[bzoj1910] [Ctsc2002] Award 颁奖典礼

  应该是第一次写这种图形类的DP。。

  一个“I”可以分成三个矩形。。令f[1..3][i][j][k]表示第几个矩形,下边界为第i行的j~k列,的最大面积。

  然后就是各种优化啊什么的。。。时间复杂度O(nm²)

  一开始一个辅助的区间DP写挂然后调了半天TAT

 #include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
const int inf=;
int f[][][maxn][maxn];
int sm[maxn][maxn],mx1[maxn][maxn],mx2[maxn][maxn];
int n,m,pre,now,ans,tmpmx; int ra;char rx;
inline int read(){
rx=getchar(),ra=;
while(rx<''||rx>'')rx=getchar();
while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int main(){
register int i,j,k;
n=read(),m=read();
for(i=;i<=n;i++)
for(j=;j<=m;j++)sm[i][j]=sm[i][j-]+read();
for(i=;i<=m;i++)sm[][i]=i; now=,pre=;
for(i=;i<=;i++)memset(f[][i],,sizeof(f[][i]));
for(i=;i<=n;i++,swap(now,pre)){
for(j=;j<m;j++)for(k=j+;k<=m;k++)
if(sm[i][k]==sm[i][j-])
f[now][][j][k]=(sm[i-][k]==sm[i-][j-]?f[pre][][j][k]:)+k-j+;
else f[now][][j][k]=-inf; for(j=;j<m;j++)for(k=m,tmpmx=-inf;k>j;k--)
tmpmx=max(tmpmx,f[pre][][j][k]),
mx1[j][k]=max(mx1[j-][k],tmpmx);
for(j=;j<m;j++)for(k=j;k<m;k++)
if(sm[i][k]==sm[i][j-]){
f[now][][j][k]=f[pre][][j][k]+k-j+;
if(sm[i-][k+]==sm[i-][j-])
f[now][][j][k]=max(f[now][][j][k],mx1[j-][k+]+k-j+);
}
else f[now][][j][k]=-inf; for(j=;j<m;j++)mx2[j][j]=f[pre][][j][j];
for(j=;j<m;j++)
for(k=;k<m-j;k++)
mx2[k][k+j]=max(mx2[k][k+j-],max(mx2[k+][k+j],f[pre][][k][k+j])); for(j=;j<m;j++)for(k=j+;k<=m;k++){
if(sm[i][k]==sm[i][j-])
f[now][][j][k]=max(f[pre][][j][k],mx2[j+][k-])+k-j+;
else f[now][][j][k]=-inf;
if(f[now][][j][k]>ans)ans=f[now][][j][k];
}
}
printf("%d\n",ans);
return ;
}
上一篇:NPOI 笔记


下一篇:selenium 右键另存为操作