題目鏈接

https://www.lydsy.com/JudgeOnline/problem.php?id=1910

題解

記$f[i][l][r][k]$表示第$i$行，$[l,r]$的部分被用來構(gòu)成第$k$個矩形，轉(zhuǎn)移：
f[i][l][r][0]=max?(0,f[i?1][l][r][0])+(r?l+1)f[i][l][r][1]=max?(0,f[i?1][l][r][1],max?a&lt;l,b&gt;rf[i?1][a][b][0])+(r?l+1)f[i][l][r][2]=max?(0,f[i?1][l][r][2],max?a&gt;l,b&lt;r,a≤bf[i?1][a][b][1])+(r?l+1) f[i][l][r][0]=\max(0,f[i-1][l][r][0])+(r-l+1)\\ f[i][l][r][1]=\max(0,f[i-1][l][r][1],\max_{a&lt;l,b&gt;r} f[i-1][a][b][0])+(r-l+1)\\ f[i][l][r][2]=\max(0,f[i-1][l][r][2],\max_{a&gt;l,b&lt;r,a\leq b} f[i-1][a][b][1])+(r-l+1) f[i][l][r][0]=max(0,f[i?1][l][r][0])+(r?l+1)f[i][l][r][1]=max(0,f[i?1][l][r][1],a<l,b>rmax?f[i?1][a][b][0])+(r?l+1)f[i][l][r][2]=max(0,f[i?1][l][r][2],a>l,b<r,a≤bmax?f[i?1][a][b][1])+(r?l+1)
其中第$i$行第$l$列到第$r$列的值都是0。

代碼

#include <cstdio> #include <cstring> #include <algorithm>int read() {int x=0,f=1;char ch=getchar();while((ch<'0')||(ch>'9')){if(ch=='-'){f=-f;}ch=getchar();}while((ch>='0')&&(ch<='9')){x=x*10+ch-'0';ch=getchar();}return x*f; }const int maxn=200;int n,m,f[2][maxn+10][maxn+10][3],p[maxn+10][maxn+10],mx[maxn+10],ans;int main() {n=read();m=read();for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){p[i][j]=read();}}for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){p[i][j]+=p[i][j-1];}}memset(f[1],-63,sizeof f[1]);for(int l=1; l<=m; ++l){for(int r=l; r<=m; ++r){if(p[1][r]-p[1][l-1]){break;}f[1][l][r][0]=r-l+1;}}for(int i=2; i<=n; ++i){memset(f[i&1],-63,sizeof f[i&1]);for(int l=1; l<=m; ++l){for(int r=l; r<=m; ++r){if(p[i][r]-p[i][l-1]){break;}f[i&1][l][r][0]=std::max(f[(i-1)&1][l][r][0],0)+(r-l+1);}}memset(mx,-63,sizeof mx);for(int l=1; l<=m; ++l){for(int r=m; r>=l; --r){mx[r]=std::max(mx[r],std::max(mx[r+1],f[(i-1)&1][l-1][r][0]));}for(int r=l; r<=m; ++r){if(p[i][r]-p[i][l-1]){break;}f[i&1][l][r][1]=std::max(f[(i-1)&1][l][r][1],mx[r+1])+(r-l+1);}}memset(mx,-63,sizeof mx);for(int l=m; l; --l){for(int r=l+1; r<=m; ++r){mx[r]=std::max(mx[r],std::max(mx[r-1],f[(i-1)&1][l+1][r][1]));}for(int r=l+2; r<=m; ++r){if(p[i][r]-p[i][l-1]){break;}f[i&1][l][r][2]=std::max(f[(i-1)&1][l][r][2],mx[r-1])+(r-l+1);ans=std::max(ans,f[i&1][l][r][2]);}}}printf("%d\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Canopus-wym/p/10376131.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1910 [Ctsc2002] Award 颁奖典礼的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。