P7365 题解
Binaerbaka
·
·
题解
描述
这道题是一个较为细节的 dp 题目。
细节部分在于它足足有四个转移方程所以及其细节。
洛谷博客版。
题意
在给定网格 0 1 中找出最大的 I 形的 0 部分，输出最大网格区块。
先前定义
我们需要用两类数组来方便转移。
-
-
注:为什么要利用新数组来辅助计算呢，因为在运行过程中，我们需要不断枚举每个 l,r 区间的最大值来进行转移方程，若如此，复杂度将会达到惊人的 O(n^4) ，但实际上这里的计算与 dp 的计算是独立的，当前互相不干扰的，所以可以提前储存，来降低复杂度。
理解
由于 I 的独特性质(上面部分大于中间部分，中间部分小于下面部分)所以我们需要去分类三种情况去讨论各自的转移方程。
-
上面部分 （P1） 可以直接在进行 dp 的转移，无需用到第二个数组 所以它只要跑 P1 循环 不必进行 f 的更新。
-
中间部分 （P2） 需要利用 f 数组辅助 dp 转移，而且它转移需要符合如下规则：
- $f_{l,r,2}$ 是由 $dp_{x,l,r,2}$ 向下转移的，由于 $P2$ 水平格子数一定小于 $P3$ ( $I$ 的下部分要出头)，所以它就应该往两边转移，则取 $\max(f_{l+1,r},f_{l,r-1})$ 并且与原 $dp$ 数组做比较，即方程为
$f_{l,r,2}=\max(dp_{id,l,r,2},\max(f_{l+1,r,2},f_{l,r-1,2})$。
-
下面部分 （P3) 与中间部分相似，但是它只要利用 f 来求出当前 dp 就可以直接求 ans 值了 所以只需要跑 P3 部分即可
-
额外：由于我们需要去来判断某一区间内是否是空的，可以利用前缀和来计算，只要 sum_R-sum_{L-1} = 0 则为空。
利用图片与代码来方便理解。
不知道各位能不能理解。
由于 P1 部分大于 P2 部分，所以我们需要将 L-1 与 R+1 的 f 部分转移到 dp_{L,R} 中 因而有方程
同理
由于 $P2$ 部分小于 $P3$ 部分，所以我们的 $dp_{L,R}$ 的部分需要由 $L+1$ 和 $R-1$ 的 $f$ 部分中转移得到 因而有方程
$dp_{id,1,r,3}=\max(Dp_{id,1,r,3},f_{l+1,r-1,2}+len)$。
最后对 $dp_{id,l,r,3}$ 取一个最大值即为答案。
自此 所有的转移方程部分已经结束，下面便是代码。
## Std
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e2+5;
int n,m,id,x,ans;
int dp[2][maxn][maxn][4];
int sum[maxn];
int f[maxn][maxn][3];//用来辅助计算 p2 跟 p3 的最值。
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m;
memset(f,-0x3f3f3f,sizeof(f));
memset(dp,-0x3f3f3f,sizeof(dp));
for(int i=1,x;i<=n;i++){
for(int j=1,x;j<=m;j++)cin>>x,sum[j]=sum[j-1]+x;//维护前缀和。
memset(dp[id],-0x3f3f3f,sizeof(dp[id]));//在“建立”完新数组之后 初始化。
for(int p=3;p>=1;p--){
for(int l=1;l<=m;l++){//遍历左区间
for(int r=l;r<=m;r++){//遍历右区间
if(sum[r]-sum[l-1]==0){
int len=r-l+1;
if(p==1)dp[id^1][l][r][1]=max(dp[id^1][l][r][1],0);//初始化数组 在跑 p1 时 初始化为 0 或保留原值。
dp[id][l][r][p]=dp[id^1][l][r][p]+len;//如果先前数组有大于 0 的值，则继承并加上长度，否则不变。
if(p==2)dp[id][l][r][2]=max(dp[id][l][r][2],f[l-1][r+1][1]+len);//方程 3 得。
if(p==3)dp[id][l][r][3]=max(dp[id][l][r][3],f[l+1][r-1][2]+len);//方程 4 得。
}
}
}
if(p==1)
for(int l=1;l<=m;l++)
for(int r=m;r>=l;r--)
f[l][r][1]=max(dp[id][l][r][1],
max(f[l-1][r][1],f[l][r+1][1]));//方程 1 得。
if(p==2)
for(int l=m;l>=1;l--)
for(int r=l;r<=m;r++)
f[l][r][2]=max(dp[id][l][r][2],
max(f[l+1][r][2],f[l][r-1][2]));//方程 2 得。
if(p==3)
for(int l=1;l<=m;l++)
for(int r=1;r<=m;r++)
ans=max(ans,dp[id][l][r][3]);//取最大值。
}
id^=1;//转换到新数组上。
}
cout<<ans;
return 0;
}
```
祝大家早日 AC。
##### 实在理解不了的话，记得手跑代码试试哦。