正题
题目链接:https://www.luogu.com.cn/problem/P3335
题目大意
给出 n × m n\times m n×m的网格,每个格子有权值。一个回路在格子的边上,要求有 2 × k 2\times k 2×k次左转,其他都是右转,且最后 2 2 2次一定得是右转。
求包含的格子权值和最大。
1 ≤ n , m ≤ 100 , 0 ≤ k ≤ 10 1\leq n,m\leq 100,0\leq k\leq 10 1≤n,m≤100,0≤k≤10
解题思路
看起来很像插头 d p dp dp对吧,但是因为最后两下得是右转所以不是插头 d p dp dp。
画一下不难发现包围出来的图形的底部一定是平的,然后上面是一个凹凸的形状。且会有 k + 1 k+1 k+1个凸, k k k个凹。也就是将固定的底部划分成 2 × k + 1 2\times k+1 2×k+1个凹凸相间的矩形。
先枚举一个底部,然后考虑 d p dp dp。设 f j , p , h f_{j,p,h} fj,p,h表示现在到第 j j j列,第 p p p个正方形,高度为 h h h时的最大权值。
转移的时候根据 p p p的奇偶性决定是在上还是在下,当然也可以直接延长这个矩形。
做个前缀和优化就是 O ( n 2 m k ) O(n^2mk) O(n2mk)的了
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int n,m,k,a[N][N],s[N][N],f[N][30][N],g[N][30][N][2],ans;
int main()
{
scanf("%d%d%d",&n,&m,&k);k=k*2+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
s[i][j]=s[i-1][j]+a[i][j];
}
for(int p=1;p<=k;p++)
for(int h=1;h<=n;h++)
f[0][p][h]=g[0][p][h][0]=g[0][p][h][1]=-1e9;
ans=-1e9;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
for(int p=1;p<=k;p++){
for(int h=1;h<=i;h++)
f[j][p][h]=max(f[j-1][p][h],g[j-1][p-1][h][p&1])+s[i][j]-s[i-h][j];
g[j][p][1][1]=g[j][p][i][0]=-1e9;
for(int h=i-1;h>=1;h--)
g[j][p][h][0]=max(g[j][p][h+1][0],f[j][p][h+1]);
for(int h=2;h<=i;h++)
g[j][p][h][1]=max(g[j][p][h-1][1],f[j][p][h-1]);
}
for(int h=1;h<=i;h++)
ans=max(ans,f[j][k][h]);
}
printf("%d\n",ans);
return 0;
}