【uoj125】 NOI2013—书法家

http://uoj.ac/problem/125 (题目链接)

题意

　　在网格上写“NOI”，每个格子上有一些权值，要求覆盖的权值最大。书写有一些规则。

Solution

　　将“NOI”分成11个部分，每个部分都是有几个有相同特点的矩形构成的，按列dp前缀最大值优化一下即可。看起来很难码的样子，其实套路都差不多，但是想清楚，一些细节处理到位，平时习惯好一点就可以很快写完辣。

　　${f[p][i][j][k]}$表示第${p}$个部分，正在dp第${i}$列，矩形上边界为${j}$，下边界为${k}$时，最大权值。

　　${mx[p][i][j][k]}$表示的是第${p}$个部分，第${i}$列，与上边界${j}$，下边界${k}$相关的前缀最大值。

　　其实比较恶心的就是第二部分，你需要处理出这样的一个前缀最大值：上边界的区间在${[1,j]}$，下边界的区间在${[j+1,k]}$。这个并不好直接求出来，所以我们把它分成两部分：上边界区间在${[1,j]}$，下边界固定在${j+1}$；以及上边界在${[1,j]}$，下边界在${[j,k]}$。这样就非常好处理了。

　　第${i}$列那一维再滚动一下就好了。

细节

　　初始化什么的。然后${j,k}$按照它们的意义${for}$过去可能会清晰一些吧。

代码

// uoj125

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<ctime>

#define LL long long

#define inf (1ll<<30)

#define MOD 1000000007

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=160,maxm=510;

int a[maxn][maxm],s[maxm][maxn],up[maxn];

int f[12][maxn][maxn],g[12][maxn][maxn],mx[12][maxn][maxn];

int n,m;

int main() {

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++)

		for (int j=1;j<=m;j++) scanf("%d",&a[i][j]);

	for (int j=1;j<=m;j++)

		for (int i=1;i<=n;i++) s[j][i]=s[j][i-1]+a[i][j];

	for (int i=0;i<=11;i++)

		for (int j=0;j<=n+1;j++)

			for (int k=0;k<=n+1;k++) f[i][j][k]=g[i][j][k]=mx[i][j][k]=-inf;

	for (int i=0;i<=n+1;i++) up[i]=-inf;

	int ans=-inf;

	for (int i=1;i<=m;i++) {

		//第1部分

		for (int j=1;j<=n;j++)

			for (int k=j;k<=n;k++)

				f[1][j][k]=max(g[1][j][k],0)+s[i][k]-s[i][j-1];

		//第2部分

		for (int j=1;j<=n;j++)

			for (int k=n;k>=j;k--) mx[1][j][k]=max(g[1][j][k],mx[1][j][k+1]);

		for (int k=1;k<=n;k++) {

			up[k]=-inf;

			for (int j=1;j<=k;j++) up[k]=max(up[k],g[2][j][k]);

		}

		for (int k=1;k<=n;k++)

			for (int j=1;j<=k;j++) mx[2][j][k]=max(mx[2][j-1][k],g[2][j][k]);

		for (int j=1;j<=n;j++)

			for (int k=j;k<=n;k++) mx[2][j][k]=max(mx[2][j][k-1],mx[2][j][k]);

		for (int j=1;j<=n;j++)

			for (int k=j;k<=n;k++)

				f[2][j][k]=max(up[j-1],max(mx[1][j][k+1],mx[2][j][k]))+s[i][k]-s[i][j-1];

		//第3部分

		for (int k=1;k<=n;k++)

			for (int j=k;j>=1;j--) mx[2][j][k]=max(mx[2][j+1][k],g[2][j][k]);

		for (int j=1;j<=n;j++)

			for (int k=j;k<=n;k++)

				f[3][j][k]=max(g[3][j][k],mx[2][j+1][k])+s[i][k]-s[i][j-1];

		//第4部分

		f[4][0][0]=g[4][0][0];

		for (int j=1;j<=n;j++)

			for (int k=j;k<=n;k++) f[4][0][0]=max(f[4][0][0],g[3][j][k]);

		//第5部分

		for (int j=1;j<=n;j++)

			for (int k=j+2;k<=n;k++) f[5][j][k]=g[4][0][0]+s[i][k]-s[i][j-1];

		//第6部分

		for (int j=1;j<=n;j++)

			for (int k=j+2;k<=n;k++) f[6][j][k]=max(g[5][j][k],g[6][j][k])+s[i][j]-s[i][j-1]+s[i][k]-s[i][k-1];

		//第7部分

		for (int j=1;j<=n;j++)

			for (int k=j+2;k<=n;k++) f[7][j][k]=g[6][j][k]+s[i][k]-s[i][j-1];

		//第8部分

		f[8][0][0]=g[8][0][0];

		for (int j=1;j<=n;j++)

			for (int k=j+2;k<=n;k++) f[8][0][0]=max(f[8][0][0],g[7][j][k]);

		//第9部分

		for (int j=1;j<=n;j++)

			for (int k=j+2;k<=n;k++) f[9][j][k]=max(g[9][j][k],g[8][0][0])+s[i][j]-s[i][j-1]+s[i][k]-s[i][k-1];

		//第10部分

		for (int j=1;j<=n;j++)

			for (int k=j+2;k<=n;k++) f[10][j][k]=max(g[10][j][k],g[9][j][k])+s[i][k]-s[i][j-1];

		//第11部分

		for (int j=1;j<=n;j++)

			for (int k=j+2;k<=n;k++) {

				f[11][j][k]=max(g[10][j][k],g[11][j][k])+s[i][j]-s[i][j-1]+s[i][k]-s[i][k-1];

				ans=max(ans,f[11][j][k]);

			}

		//滚动

		for (int j=1;j<=11;j++)

			for (int k=0;k<=n;k++)

				for (int l=0;l<=n;l++) g[j][k][l]=f[j][k][l];

	}

	printf("%d\n",ans);

	return 0;

}