[SDOI2014] LIS
题目描述
给定序列 $A$,序列中的每一项 $A_i$ 有删除代价 $B_i$ 和附加属性 $C_i$。请删除若干项,使得 $A$ 的最长上升子序列长度减少至少 $1$,且付出的代价之和最小,并输出方案。
如果有多种方案,请输出将删去项的附加属性排序之后,字典序最小的一种。
输入输出格式
输入格式
输入包含多组数据。
输入的第一行包含整数 $T$,表示数据组数。接下来 $4T$ 行描述每组数据。
每组数据的第一行包含一个整数 $N$,表示 $A$ 的项数。
接下来三行,每行 $N$ 个整数 $A_1\sim A_n$,$B_1\sim B_n$,$C_1\sim C_n$,满足 $1\le A_i,B_i,C_i \le 10^9$,且 $C_i$ 两两不同。
输出格式
对每组数据,输出两行。第一行包含两个整数 $S,M$,依次表示删去项的代价和与数量;接下来一行 $M$ 个整数,表示删去项在 $A$ 中的的位置,按升序输出。
输入输出样例
输入样例 #1
1
6
3 4 4 2 2 3
2 1 1 1 1 2
6 5 4 3 2 1
输出样例 #1
4 3
2 3 6
说明
【样例说明】
删去 $(A_2,A_3,A_6),(A_1,A_6),(A_2,A_3,A_4,A_5)$ 等都是合法的方案,但$(A_2,A_3,A_6)$ 对应的 $C$ 值的字典序最小。
对于 $100\%$ 的数据,$1\le N\le 700$,$1\le T\le 5$。