折纸

Description

现在有一个1×1的小格子分割的矩形纸片,每个小格子内包含一个整数.
现在你可以进行一系列的折叠,每次折叠的折痕必须是分隔两行或两列小格子的分割线.
折叠完之后所有重叠的小格子被看做一个单独的格子并且这个格子的价值为重点的小格子的价值和.
你想要知道在所有可能得到的新格子中格子价值的最大值是多少?

Input

第一行有两个整数,n和m,分别表示初始的矩形的长和宽.
接下来的n行,每行有m个数字,表示初始的小格子内的整数.

Output

输出一行表示所能得到的格子价值的最大值,对于100%的数据格子数字权值的绝对值不超过10000.

Sample Input

2 2
1 -3
3 -1

Sample Output

4

Code

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 25;
const int maxm = 505;
const int INF = 1000000007;
int n, m, a[maxn][maxm], sum[maxm], f[maxm], ans;
void solve(int pos) {
	for (int i = 1; i <= m; ++i) sum[i] += a[pos][i];
	int tmp[2] = {-INF, -INF};
	for (int i = 1; i <= m; ++i) {
		f[i] = sum[i];
		if (tmp[(i & 1) ^ 1] > 0) f[i] += tmp[(i & 1) ^ 1];
		tmp[i & 1] = max(tmp[i & 1], f[i]);
		ans = max(ans, f[i]);
	}
	for (int i = pos + 1; i <= n; i += 2) solve(i);
	for (int i = 1; i <= m; ++i) sum[i] -= a[pos][i];
}
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]);
	ans = -INF;
	for (int i = 1; i <= n; ++i) solve(i);
	printf("%d", ans);
	return 0;
}

 

Show Comments