bzoj1910:[Ctsc2002] Award 颁奖典礼(图形类DP)

Author Avatar
Sakits 3月 12, 2018

题解

  第一次写图形类DP…
  显然字母II可以看成三个矩形,并且第一个和第三个的宽度要比第二个要大。
  设f(x,i,j,k)f(x,i,j,k)为前xx个矩形,当前到第ii行,第xx个矩阵底边为j...kj...k的最大面积,转移比较好想。
  先预处理出g2(i,j,k)g_2(i,j,k)表示满足x<jx<jk<yk<y的最大f(i,x,y)f(i,x,y)g3(i,j,k)g_3(i,j,k)表示满足j<xj<xy<ky<k的最大f(i,x,y)f(i,x,y),则有:

f[1][i][j][k]=max(f[1][i1][j][k],0)+kj+1f[2][i][j][k]=max(f[2][i1][j][k],g2[i1][j][k])+kj+1f[3][i][j][k]=max(f[3][i1][j][k],g3[i1][j][k])+kj+1\begin{gathered} f[1][i][j][k]=max(f[1][i-1][j][k], 0)+k-j+1\\ f[2][i][j][k]=max(f[2][i-1][j][k], g2[i-1][j][k])+k-j+1\\ f[3][i][j][k]=max(f[3][i-1][j][k], g3[i-1][j][k])+k-j+1 \end{gathered}

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=210, inf=1e9;
int n, m, ans;
int mp[maxn][maxn], f[4][maxn][maxn][maxn], g2[maxn][maxn][maxn], g3[maxn][maxn][maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline int max(int a, int b){return a>b?a:b;}
int main()
{
	read(n); read(m);
	memset(f, 200, sizeof(f));
	memset(g2, 200, sizeof(g2));
	memset(g3, 200, sizeof(g3));
	for(int i=1;i<=m;i++)
	for(int j=1;j<=m;j++) f[1][0][i][j]=0;
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++) read(mp[i][j]), mp[i][j]+=mp[i][j-1];
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	for(int k=j;k<=m;k++)
	if(mp[i][k]-mp[i][j-1]==0) f[1][i][j][k]=max(f[1][i-1][j][k], 0)+k-j+1;
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	for(int k=m;k;k--)
	g2[i][j][k]=max(f[1][i][j-1][k+1], max(g2[i][j-1][k], g2[i][j][k+1]));
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	for(int k=j;k<=m;k++)
	if(mp[i][k]-mp[i][j-1]==0) f[2][i][j][k]=max(f[2][i-1][j][k], g2[i-1][j][k])+k-j+1;
	
	for(int i=1;i<=n;i++)
	for(int j=m;j;j--)
	for(int k=j;k<=m;k++)
	g3[i][j][k]=max(f[2][i][j+1][k-1], max(g3[i][j+1][k], g3[i][j][k-1]));
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	for(int k=j;k<=m;k++)
	if(mp[i][k]-mp[i][j-1]==0)
	{
		f[3][i][j][k]=max(f[3][i-1][j][k], g3[i-1][j][k])+k-j+1;
		ans=max(ans, f[3][i][j][k]);
	}
	
	printf("%d\n", ans);
}