#P3532. [Sdoi2014]Lis

    ID: 2532 传统题 1000ms 512MiB 尝试: 1436 已通过: 375 难度: 9 上传者: 标签>难度分类省选/NOI-排序与序列处理最长上升子序列动态规划线性 DP图论最小割建模拆点限制点容量Dinic最大流最小割定理残量网络贪心排序贪心枚举与搜索广度优先搜索CF2600

[Sdoi2014]Lis

[SDOI2014] LIS

题目描述

给定长度为 NN 的序列 AA。删除第 ii 项需要支付代价 BiB_i,该项还有一个附加属性 CiC_i。请删除若干项,使剩余序列的最长严格上升子序列长度至少减少 11,并使删除代价之和最小。

若有多种最小代价方案,将各方案中删去项的 CiC_i 分别按升序排成序列,选择该序列字典序最小的方案。

输入格式

第一行一个整数 TT,表示数据组数。接下来每组数据占四行。

第一行一个整数 NN。第二、三、四行各有 NN 个整数,依次给出 A1,…,ANA_1,\ldots,A_N、B1,…,BNB_1,\ldots,B_N、C1,…,CNC_1,\ldots,C_N。

输出格式

每组数据输出两行。第一行两个整数 S,MS,M,分别表示删除代价之和和删去的项数。第二行输出删去项在原序列中的 MM 个下标,按升序排列,下标从 11 开始。

样例 #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

删去 {A2,A3,A6}\{A_2,A_3,A_6\}、{A1,A6}\{A_1,A_6\}、{A2,A3,A4,A5}\{A_2,A_3,A_4,A_5\} 都能以最小代价完成任务,其中第一种方案的属性升序序列字典序最小。

数据范围

1≤T≤51\le T\le5,1≤Ai,Bi,Ci≤1091\le A_i,B_i,C_i\le10^9,且 CiC_i 两两不同。

原赛测试点 NN
1–3 1≤N≤201\le N\le20
4–6 1≤N≤2001\le N\le200
7–10 1≤N≤7001\le N\le700

原赛评分

每个测试点取满足条件的最高一档分数。

分值 条件
30%30\% 输出符合格式,所有数据组的 SS 均正确
50%50\% 所有数据组的 SS 均正确,且每组输出的方案均合法
100%100\% 输出与答案完全相同