#P18719. One, Two, Three
One, Two, Three
One, Two, Three
给定一个长度为 的整数序列 ,每个元素均为 、 或 。第 个元素还有一个正整数美丽值 。
你可以任意次(也可以零次)执行如下操作:选择当前序列中连续的一段,如果这一段的元素之和等于 或 ,则将整段删除。每次删除后,剩余的左、右两部分立即拼接成一个连续序列。
你需要先使最终剩余元素的数值之和最小;在达到这个最小值的所有方案中,再使剩余元素的美丽值之和最大。
输入格式
第一行一个整数 ,表示测试用例数,。
每个测试用例包含四行:
- 第一行一个整数 ,。
- 第二行一个长度为 、不含空格的字符串 。每个字符为
1、2或3,表示原始序列。 - 第三行 个整数 ,。
- 第四行一个整数 ,,表示此用例的类型。
所有测试用例的 之和不超过 。
输出格式
对每个测试用例,先输出两个整数:最终剩余元素的最小数值之和,以及在此条件下剩余元素的最大美丽值之和。
如果 ,该用例的输出到此结束。
如果 ,还要输出达到这两个值的一种操作序列:下一行输出操作次数 ,之后 行描述各次操作。每行先输出此次删除的元素个数,随后按递增顺序输出这些元素在初始序列中的下标,下标从 开始。
每次列出的元素必须在该次操作前的当前序列中连续,并且数值之和为 或 。被删除的元素不能再次使用。 可以为 ;此时其后没有操作行。允许输出任意满足要求且达到上述两级最优目标的方案。
原样例
6
3
121
1 2 3
2
3
221
4 5 6
2
3
123
7 8 9
1
6
123221
10 11 12 13 14 15
2
6
312322
15 14 13 12 11 10
2
6
213312
9 8 7 5 5 1
2
0 0
1
3 1 2 3
1 6
1
2 1 2
6 24
3 29
1
4 1 2 3 4
5 25
2
2 5 6
2 1 2
0 0
3
2 2 3
2 4 5
2 1 6
样例第六个用例中,先删除原下标 ,再删除原下标 ,此后原下标 在当前序列中相邻,因此最后一步可以删除它们。输出下标始终是原下标,不能改成操作时的位置。