思路倒是挺不错
找到了一道比较奇怪的利用了“费用提前计算”方法的题目
Part1. 题面
有 3 种球,分别标记为 R,G,B。每种球各有 n 个,这 3n 个球排成一行。
现在将这 3n 个球分成 n 组,使得每一组中每种球恰有一个。每个分组的代价为该组球中相隔最远的两个球的距离。
问有多少种不同的分组方式,使得分组的总代价最小(两种方式被考虑为不同当且仅当至少有一个组中有不同的球)。
数据规模:$1\le n\le10^5$。
Part2. 题解
Part2/1. 怎样计算最小值
要知道最小值的方案数,首先要知道最小值怎么算。不妨考虑一种非常暴力的 DP:dp[i][a][b][c][d][e][f]
表示:前 i 个球中,3 种球各有 a,b,c 个没有配对(已经被分到组中的球就叫“已配对”),(R,G) 配对了 d 对,(R,B) 配对了 e 对,(G,B) 配对了 f 对。
但是我们发现这样似乎不能转移,因为我们不知道未配对的球的位置,也就无法计算距离。其实是可以转移的,这里就要用到“费用提前计算”了,转移分为三种(不妨设当前考虑的球为 R,对应的数量是 a;其他两种情况是一样的):
不配对:
dp[i][a+1][b][c][d][e][f]=dp[i-1][a][b][c][d][e][f]+(a+b+c+d+e+f)
后面的
a+b+c+d+e+f
就是费用提前计算了——这已经存在的 a+b+c 个球和 d+e+f 对球仍未完成分组,必然会增加 1 的花费。与 G 配对:
dp[i][a][b-1][c][d+1][e][f]=dp[i-1][a][b][c][d][e][f]+(a+b+c+d+e+f)
与 B 配对是类似的。
与一对 (G,B) 配对:
dp[i][a][b][c][d][e][f-1]=dp[i-1][a][b][c][d][e][f]+(a+b+c+d+e+f)
以上只是帮助理解贪心的正确性,代码实现中并不会体现这一段——不难发现,我们要 让 a+b+c+d+e+f 尽可能小 才可能使 dp 值更优。因此,当我们拿到一个 R 球,如果有一对未配对的 G,B 球,一定会配对成一组;如果有单个未配对的 G 或 B,一定会与它组成一对,即固定为分在同一组中。
Part2/2. 贪心
于是就有了一个非常easy的贪心:记录 3 种球在之前有多少个未完成分组,显然不会同时有 3 种球未完成分组。
考虑当前这个球,如果能够和之前未配对的球配对,那就配对了。又因为推导这个贪心结论时,我们是利用动态规划的“费用提前计算”,所以当前的球具体与前面的哪两个球配对并不重要,因此组合数算一算即可。
如果无法配对,那就更改未配对的球的数量。
这样扫一遍 $O(n)$,可以 AC 了。(其实难点在证明这个贪心是正确的)
Part3. 源代码
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
啊哈?又完成一篇 blog 了呢!