#P3532. [Sdoi2014]Lis
[Sdoi2014]Lis
[SDOI2014] LIS
题目描述
给定长度为 的序列 。删除第 项需要支付代价 ,该项还有一个附加属性 。请删除若干项,使剩余序列的最长严格上升子序列长度至少减少 ,并使删除代价之和最小。
若有多种最小代价方案,将各方案中删去项的 分别按升序排成序列,选择该序列字典序最小的方案。
输入格式
第一行一个整数 ,表示数据组数。接下来每组数据占四行。
第一行一个整数 。第二、三、四行各有 个整数,依次给出 、、。
输出格式
每组数据输出两行。第一行两个整数 ,分别表示删除代价之和和删去的项数。第二行输出删去项在原序列中的 个下标,按升序排列,下标从 开始。
样例 #1
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
删去 、、 都能以最小代价完成任务,其中第一种方案的属性升序序列字典序最小。
数据范围
,,且 两两不同。
| 原赛测试点 | |
|---|---|
| 1–3 | |
| 4–6 | |
| 7–10 |
原赛评分
每个测试点取满足条件的最高一档分数。
| 分值 | 条件 |
|---|---|
| 输出符合格式,所有数据组的 均正确 | |
| 所有数据组的 均正确,且每组输出的方案均合法 | |
| 输出与答案完全相同 |