早该意识到一个占位的罗马数字不够用……
感觉这场的 T2 比较玄(dú)乎(líu)，就 pass 了
但是为什么每次 T2 都是全场最难的啊 ╮(╯-╰)╭
# 题面
T1. 多水缩合(water)
有 $n$ 个数字 $a_1,\dots,a_n$ 从左到右排列，在给定一个“缩合”参数 $t$。你可以进行以下两种操作：
- 在任意位置（包括开头末尾）添加一个任意数字，花费为 $1$。
- 选取一段长度大于等于 $t$ 的连续相同数字删去，花费为 $0$。
求删去所有数字的最小花费。
$1\le n,a_i\le100$，$2\le t\le 5$。
T3. 淋巴炮塔(turret)
有一个 $n\times m$ 的矩阵，矩阵上的每个位置 $a_{i,j}$ 可能是以下三种情况：
- $a_{i,j}=0$，该位置为空；
- $a_{i,j}<0$，该位置有一个炮塔，此时 $a_{i,j}=-1,-2,-3,-4$ 分别对应该炮塔的朝向为“向上，向下，向左，向右”；
- $a_{i,j}>0$，该位置有 $a_{i,j}$ 个敌人。
每个炮塔可以攻击它所在朝向的一个位置的敌人，此时它的“攻击轨道”为 从炮塔位置到敌人位置的一条线段。并且两个炮塔的攻击轨道不能交叉。
保证对于任意一个炮塔，其朝向上不会有任何一座其他炮塔。
求攻击的敌人的最大数量。
$1\le n,m\le50$，$a_{i,j}\le10^3$，$\sum[c_{i,j}<0]<10^{3}$。
# 解析
可以发现 T1,T3 的 $n,m$ 都非常的小 :)
T1. 多水缩合
第一步非常关键——把所有可能的操作归类：
- 直接消去区间的开头；
- 先把中间的一段区间（可以是空区间）消去，使得剩下的两个位置拼起来得到一个大的段；
- 在某个位置的左边添加数字（因为我们添加数字肯定是添加与旁边相同的，所以既然可以插入在一段相同的数右边，那插入在左边也是一样的）。
我们发现，只用上面描述的这三种操作一定可以得到一个最优解（也算是DP的一个常见套路，也就是找到操作的共性）。
于是根据这个，我们可以设计区间DP状态：f[i][j] 表示消除 $[i,j]$ 区间的最小花费。但是我们发现这样不方便转移——不方便处理第二类操作。
分析第二类操作，假设我们先消去了 $[l+1,r-1]$ 这样一段区间使得 $l,r$ 相邻（$a_l=a_r$），那么也就相当于在$\underline{a_r}$的左边添加了一段相同的数。
于是可以加一维：f[i][j][k] 表示当前在 $a_i$ 的左边添加了 $k$ 个和 $a_i$ 一样的数字，然后消去这段区间（包括在左边添加的数字）的最小花费。我们发现 $k$ 的范围其实只用开到 $t-1$ 这么大，因为插入了 $\ge t$ 个和 $a_i$ 相同的数字之后就会形成一个长度 $\ge t+1$ 的相同段，而只要长度为 $t$ 就可以消去了。
转移也比较简单了：
- 当 $k<t-1$ 时，在 $a_i$ 左边插入一个相同数字：
f[i][j][k]<- f[i][j][k+1]+1（<-表示和左边取 min）； - 当 $k=t-1$ 时，已经可以直接删掉最左边的 $a_i$ 了：
f[i][j][k]<- f[i+1][j][k]； - 枚举一个和 $a_i$ 相同的 $a_m$（$i<m\le j$），先删去 $[i+1,m-1]$，然后 $k+1$ 个 $a_i$ （注意要带上原来插入在 $a_i$ 左边的数）直接贴到 $a_m$ 的左边，
f[i][j][k]<- f[m][j][min(t-1,k+1)]+f[i+1][m-1][0]；
T3. 淋巴炮塔
考场思路：一眼看出最小割然后以为是最大权闭合子图（不是）。
假设不考虑轨道交叉带来的冲突，那么每个炮塔当然找它方向上敌人数量最多的位置攻击，这个也有用。先把每个位置为 $(i,j)$ 的炮塔的方向上敌人数量的最大值处理出来，记为 $p_{i,j}$。
看到这个 $n,m$ 这么小感觉就很适合网络流的玄学复杂度……也没什么特别可讲的，就直接说建图和证明吧。
- 点集包括 源点$S$、汇点$T$，矩形的每个位置 $(i,j)$ 拆成两个点 $A_{i,j}$，$B_{i,j}$；
- 源点向每个纵向攻击的炮塔 $(i,j)$ 的 $A_{i,j}$ 连边，容量 $+\infty$；
- 每个横向攻击的炮塔 $(i,j)$ 的 $B_{i,j}$ 向 $T$ 连边，容量 $+\infty$；
- 对于向上攻击的炮塔 $(i,j)$，连边 $A_{i,j}\to A_{i-1,j}\to A_{i-2,j}\to\dots\to A_{1,j}$（空位置也要连），其中 $A_{k,j}\to A_{k-1,j}$ 的边容量为 $p_{i,j}-a_{k,j}$；
- 对于向下攻击的，连边 $A_{i,j}\to A_{i+1,j}\to A_{i+2,j}\to\dots\to A_{n,j}$，其中 $A_{k,j}\to A_{k+1,j}$ 的容量为 $p_{i,j}-a_{k,j}$；
- 对于向左攻击的，连边 $B_{i,1}\to B_{i,2}\to B_{i,3}\to\dots\to B_{i,j}$，其中 $B_{i,k}\to B_{i,k+1}$ 的容量为 $p_{i,j}-a_{i,k}$；（注意是从 $(i,1)$ 连到 $(i,j)$）
- 对于向右攻击的，连边 $B_{i,n}\to B_{i,n-1}\to B_{i,n-2}\to\dots\to B_{i,j}$，其中 $B_{i,k}\to B_{i,k-1}$ 的容量为 $p_{i,j}-a_{i,k}$；
- 每个 $(i,j)$，连边 $A_{i,j}\to B_{i,j}$，容量 $+\infty$。
答案是 $\sum p_{i,j}-最小割$。
正确性可以这样理解：一条 $S$ 到 $T$ 的路径为 $S$ 到纵向炮塔、到一个位置 $A_{i,j}$、到 $B_{i,j}$、到横向炮塔、到 $T$。
那么路径上的这个位置 $A_{i,j},B_{i,j}$ 就是横向炮塔和纵向炮塔的冲突位置，横向炮塔和纵向炮塔至少有一个要在 $(i,j)$ 之前攻击（或者不攻击），而最小割就是在这条路径上选择一条边割掉。
割掉一条边意味着什么？假设割掉的是 $A_{k,j}\to A_{k+1,j}$，横向炮塔为 $(i,j)$，这条边的容量为 $p_{i,j}-a_{k,j}$。这意味着炮塔 $(i,j)$ 选择了 $(k,j)$ 攻击，因为 $p_{i,j}-(p_{i,j}-a_{k,j})=a_{k,j}$，就是 $(k,j)$ 的敌人数量。因为此时 $(i,j)$ 选择了冲突位置之前的一个位置攻击，就避免了冲突。
其他情况同理。
又因为是最小割，所以减去的一定尽可能小，那剩下的答案就是最大值。
> 总结：
像这样的最小割思路一般是“不合法的最优情况”做出一些“牺牲”使它合法，同时这点“牺牲”最小。比如这道题，一开始不考虑冲突，贪心得到的就是不合法的最优情况；我们需要舍弃一些最优位置而用其他位置，这就是牺牲；牺牲的代价就是“现在的位置-原来的最优位置”；要最小化牺牲。
# 源代码
T1. water.cpp
1 | /*Lucky_Glass*/ |
T3. turret.cpp
1 | /*Lucky_Glass*/ |