2021.11.06模拟赛

There’s a way back home

2021.11.06 模拟赛

记 $dp_{i,j,x,y}$ 表示 $i$ 个白色棋子， $j$ 个黑色棋子，后缀里白色比黑色最多多 $x$ 个，黑色比白色最多多 $y$ 个

每次枚举放那个棋子

$dp_{i,j,x,y} \to dp_{i+1,j,c+1,\max(0,d-1)}$ 白色棋

$dp_{i,j,x,y} \to dp_{i,j+1,\max(0,c-1),d+1}$ 黑色棋

考虑只需要记录当前到了第几个人，当前目标是 $c$ 剩下三个人目标为 $a,b,c$ 的状态

记忆化搜索

每次枚举送一个人到目的地或者上一个人爆搜即可

折半爆搜即可，合并的时候拿个 set 找到最大的小于 $m-\mathrm{sum}_S$ 的值合并

先考虑这个交叉的限制，像是个最小割，大力拆点，把一个点变成横竖两个方向的点，之间连一条正无穷的边

如果一个导弹能攻击肯定是攻击最大的区域，所以把导弹到攻击位置依次连边，然后横边连源点，竖边连汇点

这样最小割就能求出来无交叉最大值

但是问题是如果有一个行/列的最大值不能选不意味着全都不能选，它可以选次大值或者次次大值之类的

考虑我们答案是 $\sum a_i - \operatorname{MinCut}(G)$ 得到的 ( $a_i$ 是不考虑交叉选择的点)

我们可以把这个操作整合进 $\operatorname{MinCut}(G)$ 里，具体的，在顺次连接导弹到攻击区域的边的时候流量设置为 $a_i-p$

$p$ 是当前点的点权，这样的话如果去割到了这个边贡献会是 $+p-a_i$ 就是我们想要的