Description:

在一张每个点有价值纸上写 $NOI$ ，最大化价值。

$1 \le N \le 150$ $1 \le M \le 500$

Solution:

先将 $NOI$ 分成十一个部分。

$DP$ ， $O$ 和 $I$ 都比较好搞，对于 $N$ ，将他分成三部分，第一个竖矩形直接转移，从一个矩形转移到下一个矩形只要预处理一下 $g[i][j]$ 表示 $max(f[k][1][i][j],f[k][1][i-1][j],\cdots,f[k][1][1][j])$ ，即 $f[k][1]$ 的前缀最大值， $f[k][1][i][j]$ 从 $max(max(g[i][j+1],g[i][j],\cdots,g[i][i]),g[i-1][i-1])$ ，从第一个矩形转移到第二个矩形就求 $f[k][1][i][j]=max(f[k][0][i][j+1],f[k][0][i][j+2],\cdots,f[k][0][i][N])$ ，也处理一个前缀最大值即可，最后一个矩形也类似，最后要开滚动数组。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#define INF 0x3f3f3f3f

using namespace std;

int n,m;

#define MAXN 152

#define MAXM 502

int map[MAXM][MAXN];

int f[2][11][MAXN][MAXN];

int g[MAXM][MAXN]; 

int sum[MAXM][MAXM];

int ans = 0;

int main()

{

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

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

	{

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

		{

			scanf("%d",&map[j][i]);

		}

	}

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

	{

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

		{

			sum[i][j] = sum[i][j - 1] + map[i][j];

		}

	}

	memset(f,0xc0,sizeof(f));

	ans = -INF;

	int cur = 0,pre = 1;

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

	{

		cur = cur ^ 1;pre = pre ^ 1;

		memset(f[cur],0xc0,sizeof(f[cur]));

		//N的第一部分

		for(int i = 1;i <= n;++i)for(int j = i;j <= n;++j)f[cur][0][i][j] = max(f[pre][0][i][j],0) + sum[k][j] - sum[k][i - 1];

		//N的第二部分

		memset(g,0xc0,sizeof(g));

		for(int i = 1;i <= n;++i)for(int j = i;j <= n;++j)g[i][j] = max(f[pre][1][i][j],g[i - 1][j]);

		int t; 

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

		{

			t = g[i - 1][i - 1];

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

			{

				t = max(t,g[i][j]);

				f[cur][1][i][j] = max(f[cur][1][i][j],t + sum[k][j] - sum[k][i - 1]);

			}

			t = -INF;

			for(int j = n;j >= i;--j)

			{

				t = max(t,f[pre][0][i][j + 1]);

				f[cur][1][i][j] = max(t + sum[k][j] - sum[k][i - 1],f[cur][1][i][j]);

			}

		}

		//N第三个部分

		memset(g,0xc0,sizeof(g));

		for(int i = n;i >= 1;--i)for(int j = i;j <= n;++j)g[i][j] = max(f[pre][1][i][j],g[i + 1][j]);

		for(int i = 1;i <= n;++i)for(int j = i;j <= n;++j)f[cur][2][i][j] = max(g[i + 1][j],f[pre][2][i][j]) + sum[k][j] - sum[k][i - 1];

		//N和O之间的空列

		t = -INF;

		for(int i = 1;i <= n;++i)for(int j = i;j <= n;++j)t = max(t,f[pre][2][i][j]);

		f[cur][3][1][n] = max(t,f[pre][3][1][n]);

		//O的第一部分

		for(int i = 1;i <= n;++i)for(int j = i + 2;j <= n;++j)f[cur][4][i][j] = f[pre][3][1][n] + sum[k][j] - sum[k][i - 1];

		//O的第二部分

		for(int i = 1;i <= n;++i)for(int j = i + 2;j <= n;++j)f[cur][5][i][j] = max(f[pre][5][i][j],f[pre][4][i][j]) + map[k][i] + map[k][j];

		//O的第三部分

		for(int i = 1;i <= n;++i)for(int j = i + 2;j <= n;++j)f[cur][6][i][j] = f[pre][5][i][j] + sum[k][j] - sum[k][i - 1]; 

		//O和I之间的空列

		t = -INF;

		for(int i = 1;i <= n;++i)for(int j = i;j <= n;++j)t = max(t,f[pre][6][i][j]);

		f[cur][7][1][n] = max(t,f[pre][7][1][n]);

		//I的第一部分

		for(int i = 1;i <= n;++i)for(int j = i + 2;j <= n;++j)f[cur][8][i][j] = max(f[pre][8][i][j],f[pre][7][1][n]) + map[k][i] + map[k][j];

		//I的第二部分

		for(int i = 1;i <= n;++i)for(int j = i + 2;j <= n;++j)f[cur][9][i][j] = max(f[pre][9][i][j],f[pre][8][i][j]) + sum[k][j] - sum[k][i - 1];

		//I的第三部分

		for(int i = 1;i <= n;++i)for(int j = i + 2;j <= n;++j)f[cur][10][i][j] = max(f[pre][10][i][j],f[pre][9][i][j]) + map[k][i] + map[k][j]; 

		for(int i = 1;i <= n;++i)for(int j = i + 2;j <= n;++j)ans = max(ans,f[cur][10][i][j]);

	}

	cout << ans << endl;

	return 0;

}