TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2877
  • 問題
  • P2877【SDOI2014 R1D2】LIS
    制限 : 時間制限 : 20000 MS   メモリ制限 : 565536 KB
    問題説明

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

    入力形式

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

    出力形式

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

    サンプル入力

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

    サンプル出力

    4 3
    2 3 6 

    ヒント

    样例解释:
    删去{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\)


    ソース  感谢nodgd放题