← 返回题目

题库练习 LIS

← 上一题下一题 →

A2764 | $LIS$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定序列 $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

C++ 编辑器

输入

输出