TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2877
  • Problem
  • P2877【SDOI2014 R1D2】LIS
    Limits : Time Limit : 20000 MS   Memory Limit : 565536 KB
    Description

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

    Input Format

    输入包含多组数据。
    输入的第一行包含整数T,表示数据组数。接下来4*T行描述每组数据。
    每组数据的第一行包含一个整数N,表示A的项数。
    接下来三行,每行N个整数A1..AN,B1..BN,C1..CN,满足1<=Ai,Bi,Ci<=109,且Ci两两不同。

    Output Format

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

    Sample Input

    1
    6
    3 4 4 2 2 3 
    2 1 1 1 1 2 
    6 5 4 3 2 1 

    Sample Output

    4 3
    2 3 6 

    Hint

    样例解释:
    删去{A2,A3,A6},{A1,A6},{A2,A3,A4,A5}等都是合法的方案,但是{A2,A3,A6}对应的C值的字典序最小。

    数据规模:
    测试点1-3:1<=N<=20,T<=5
    测试点4-6:1<=N<=200,T<=5
    测试点7-10:1<=N<=700,T<=5

    Update 2020.02.25: nodgd提醒您,数据保证$1\leq A_i\leq N$,$C$是$1\sim N$的排列,\(B_1+\dots+B_n\leq 10^4\)


    Source  感谢nodgd放题