题解：P12650 [KOI 2024 Round 2] 双 v 字形涂色
lailai0916
·
·
题解
题意简述
在黑白网格上执行两次 V 字形涂色。
后一次操作遇到黑格、边界或前一次涂出的蓝格时停止。
求两次操作最多能涂蓝多少个格子。
解题思路
设 l_{i,j} 和 r_{i,j} 分别表示从白格 (i,j)
向左上、右上连续经过的白格数量。
单独以 (i,j) 为起点时，完整 V 的大小为：
w_{i,j}=l_{i,j}+r_{i,j}-1
两条斜线移动都保持 i+j 的奇偶性。
所以两个起点的奇偶性不同时，
两次操作经过的格子互不相同，也不会互相阻挡。
分别取两个奇偶类中最大的 w，即可得到这一类答案。
下面考虑起点奇偶性相同的情况。
对坐标作变换：
\begin{aligned}
x & =\frac{i+j}{2} \\
y & =\frac{i-j}{2}
\end{aligned}
固定奇偶类后，统一平移半格即可把坐标视为整数。
向左上移动会使 x 减一而保持 y，
向右上移动会使 y 减一而保持 x。
因此一个 V 变成从拐点向 x,y 负方向延伸的直角折线。
先处理两个坐标同向有序的拐点。
若第一个拐点的 x,y 都严格小于第二个，
两条负方向折线不会相交。
令 f_{i,j} 表示以 (i,j) 为底的上方三角形中，
完整 V 大小的最大值，其转移为：
f_{i,j}=\max\{f_{i-1,j-1},f_{i-1,j},f_{i-1,j+1},w_{i,j}\}
对当前起点 (i,j)，f_{i-1,j} 覆盖的起点满足：
i-i'>|j-j'|
这正好表示两个变换后的坐标都严格更小。
所以可以用 w_{i,j}+f_{i-1,j} 更新答案。
这里只依赖上一行，代码将 f 压缩为两行。
其余同奇偶拐点可以交换编号，满足
两个完整 V 可能不相交，也可能在一条横臂和一条纵臂处相交。
若先涂其中一个，另一个会在交点处停止，
留下的部分不一定还是完整 V。
为统一描述这部分，定义 $L_{i,j}$ 为从 $(i,j)$ 出发，
先向左下走若干步，再向左上走若干步的最长白色折线。
定义 $R_{i,j}$ 为左右对称的最长折线。
不走左下或右下部分也是允许的，因此有：
$$
\begin{aligned}
L_{i,j} & =\max\{l_{i,j},L_{i+1,j-1}+1\} \\
R_{i,j} & =\max\{r_{i,j},R_{i+1,j+1}+1\}
\end{aligned}
$$
从下到上扫描即可计算这两个值。
代码直接复用 $l,r$ 数组保存 $L,R$。
在变换后的坐标中，
一类方案能被某条 $y$ 坐标恒定的直线分开。
此时直线一侧是一条 $L$ 折线，另一侧是一个完整 V。
因为 $2y=i-j$，可以按 $j-i$ 建桶，
维护 $L$ 的前缀最大值与 $w$ 的后缀最大值。
另一类方案能被某条 $x$ 坐标恒定的直线分开。
此时一侧是完整 V，另一侧是一条 $R$ 折线。
因为 $2x=i+j$，可以按 $i+j$ 建桶，
维护 $w$ 的前缀最大值与 $R$ 的后缀最大值。
枚举相邻桶之间的分界线，
把两侧最大值相加即可覆盖所有剩余位置关系。
所有二维数组只扫描常数次。
时间复杂度为 $O(nm)$，空间复杂度为 $O(nm)$。
## 正确性证明
先看完整 V 的两类直接组合。
不同奇偶类中的格子不可能重合，
所以两个最大完整 V 可以同时取得。
对同一奇偶类，若两个拐点的 $x,y$ 均严格同向有序，
一个 V 的横臂位于另一条横臂下方，
纵臂也位于另一条纵臂左侧，因此不会相交。
三角形 DP 恰好枚举了所有这种拐点对。
再看 $x_1\leq x_2$ 且 $y_1\geq y_2$ 的情况。
可能的交点只能由第一个 V 的一个坐标方向线段，
与第二个 V 的另一个坐标方向线段产生。
若对应线段到不了对方坐标，两个完整 V 本来就不相交，
可以用一条固定 $x$ 或固定 $y$ 的直线分开。
若两条线段相交，先完成一侧的 V 后，
另一操作会在首次碰到蓝格时停止。
它实际涂出的格子恰好是某条先向下、再向上的 $L$ 或 $R$ 折线。
截断后的折线与完整 V 仍位于同一条分界线的两侧。
因此，任意两次操作得到的蓝格集合，
必属于不同奇偶、同向有序、按 $x$ 分离或按 $y$ 分离之一。
算法的四部分统计不会遗漏最优方案。
反过来，桶中相加的两项位于分界线两侧。
先执行完整 V，再执行另一侧对应操作时，
后一次至少能涂出预处理记录的折线路径；
若没有立即停止，只会得到更多蓝格。
三角形 DP 对应两个不相交的完整 V，
不同奇偶类中的两条路径也没有公共格子，二者都可以同时实现。
所以算法统计的每个候选都不超过某个可行方案的收益。
综上，算法得到的最大值就是答案。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=3005;
string s[N];
int l[N][N];
int r[N][N];
int w[N][N];
int f[2][N];
int pre[2][N<<1];
int suf[2][N<<1];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>s[i];
int ans=0;
int mx[2]={};
for(int i=1;i<=n;i++)
{
int now=i&1;
int last=now^1;
f[now][0]=f[now][m+1]=0;
for(int j=1;j<=m;j++)
{
if(s[i][j-1]=='1')
{
l[i][j]=l[i-1][j-1]+1;
r[i][j]=r[i-1][j+1]+1;
w[i][j]=l[i][j]+r[i][j]-1;
}
ans=max(ans,w[i][j]+f[last][j]);
f[now][j]=max({f[last][j-1],f[last][j],f[last][j+1],w[i][j]});
mx[(i+j)&1]=max(mx[(i+j)&1],w[i][j]);
}
}
ans=max(ans,mx[0]+mx[1]);
for(int i=n;i>=1;i--)
{
for(int j=1;j<=m;j++)
{
if(s[i][j-1]=='0')continue;
l[i][j]=max(l[i][j],l[i+1][j-1]+1);
r[i][j]=max(r[i][j],r[i+1][j+1]+1);
int x=n+j-i+1;
int y=i+j;
pre[0][x]=max(pre[0][x],l[i][j]);
suf[0][x]=max(suf[0][x],w[i][j]);
pre[1][y]=max(pre[1][y],w[i][j]);
suf[1][y]=max(suf[1][y],r[i][j]);
}
}
for(int k=0;k<2;k++)
{
for(int i=1;i<=n+m;i++)pre[k][i]=max(pre[k][i],pre[k][i-1]);
for(int i=n+m;i>=1;i--)suf[k][i]=max(suf[k][i],suf[k][i+1]);
for(int i=1;i<n+m;i++)ans=max(ans,pre[k][i]+suf[k][i+1]);
}
cout<<ans<<'\n';
return 0;
}
```