正題
題目連結:https://www.luogu.com.cn/problem/P3335
題目大意
給出\(n\times m\)的網格，每個格子有權值。一個回路在格子的邊上，要求有\(2\times k\)次左轉，其他都是右轉，且最後\(2\)次一定得是右轉。
求包含的格子權值和最大。
\(1\leq n,m\leq 100,0\leq k\leq 10\)
解題思路
看起來很像插頭\(dp\)對吧，但是因為最後兩下得是右轉是以不是插頭\(dp\)。
畫一下不難發現包圍出來的圖形的底部一定是平的，然後上面是一個凹凸的形狀。且會有\(k+1\)個凸，\(k\)個凹。也就是将固定的底部劃分成\(2\times k+1\)個凹凸相間的矩形。
先枚舉一個底部，然後考慮\(dp\)。設\(f_{j,p,h}\)表示現在到第\(j\)列，第\(p\)個正方形，高度為\(h\)時的最大權值。
轉移的時候根據\(p\)的奇偶性決定是在上還是在下，當然也可以直接延長這個矩形。
做個字首和優化就是\(O(n^2mk)\)的了
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;
}