题目描述

 

给定序列A，序列中的每一项Ai有删除代价Bi和附加属性Ci。请删除若干项，使得4的最长上升子序列长度减少至少1，且付出的代价之和最小，并输出方案。 如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。

 

输入输出格式

输入格式：

 

 

输入包含多组数据。 输入的第一行包含整数T，表示数据组数。接下来4*T行描述每组数据。 每组数据的第一行包含一个整数N，表示A的项数，接下来三行，每行N个整数A1．．An，B1．，Bn，C1．．Cn，满足1 < =Ai，Bi，Ci < =10^9，且Ci两两不同。

 

 

输出格式：

 

 

对每组数据，输出两行。第一行包含两个整数S，M，依次表示删去项的代价和与数量；接下来一行M个整数，表示删去项在4中的的位置，按升序输出。

 

 

 

输入输出样例

 

输入样例#1：

163 4 4 2 2 32 1 1 1 1 26 5 4 3 2 1

输出样例#1：

4 3    2 3 6解释：删去(A2，43，A6)，(A1，A6)，(A2，43，44，A5)等都是合法的方案，但{A2，43，A6)对应的C值的字典序最小。

 

说明

 

1 < =N < =700 T < =5

 

题意：

给定一个序列，删去若干项，使得序列的 LIS 长度减少，且代价和最小

输出字典序最小的方案

分析：

 

 

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;#define FRE(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);const int N=10005;const int inf=0x3f3f3f3f;struct edge{
   int v,next,cap;}e[N*100];int tot=1,head[N];struct node{
   int c,id;}c[N];int dis[N],q[N*10];int n,cas,maxflow,maxn,a[N],b[N],f[N],ans[N*10];inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    return x*f;}inline bool cmp(const node &x,const node &y){    return x.c