题面

大秦为你打开题目传送门

题目描述

帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 $n \times m$ 的矩阵，矩阵中的每个元素 $a_{i,j}$ 均为非负整数。游戏规则如下：

  1. 每次取数时须从每行各取走一个元素，共 $n$ 个。经过 $m$ 次后取完矩阵内所有元素；
  2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
  3. 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 $\times 2^i$，其中 $i$ 表示第 $i$ 次取数（从 $1$ 开始编号）；
  4. 游戏结束总得分为 $m$ 次取数得分之和。

帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。

输入格式

输入文件包括 $n+1$ 行：

第一行为两个用空格隔开的整数 $n$ 和 $m$。

第 $2\sim n+1$ 行为 $n \times m$ 矩阵，其中每行有 $m$ 个用单个空格隔开的非负整数。

输出格式

输出文件仅包含 $1$ 行，为一个整数，即输入矩阵取数后的最大得分。

样例 #1

样例输入 #1

1
2
3
2 3
1 2 3
3 4 2

样例输出 #1

1
82

提示

【数据范围】

对于 $60%$ 的数据，满足 $1\le n,m\le 30$，答案不超过 $10^{16}$。
对于 $100%$ 的数据，满足 $1\le n,m\le 80$，$0\le a_{i,j}\le1000$。

【题目来源】

NOIP 2007 提高第三题。

思路

由于这道题的 n m 数据范围到 $80$ 对于正解没有特殊意义，反而需要 __int128 或高精度卡过去，所以这里只讲 60% 的做法。

首先这道题目还是一样，由于取走每一行的开头或者末尾对于其他的行不影响，满足最优他就是最优，这就是 DP 的第一个条件，最优子结构。有了最优子结构，我们在想每次取数是在边缘取，那么每次取数完剩下来的元素一定是在一个完整的一个区间中，又是求最优解，也就是区间 DP 。

那么我们考虑到上面的操作都是针对每一行考虑的，我们不妨也每次只针对每一个行去做 DP 。

我们用 $dp_{i,j}$ 表示区间变为 $[i, j]$ 时获得的最大分数。那么我们就考虑这个取数之前只可能是左边多一个或者右边多一个，那就是从这两个转移了。

答案的话，由于这个空的区间我们的 DP 似乎是推不到的，所以说就要找出所有长度为 1 的区间取最大值作为这一行的价值，然后所有行加起来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 int128;

namespace FastIO {
	template<typename Tp>
	inline void read(Tp &x) {
		char ch;
		int flag = 0;
		x = 0;
		while(!isdigit(ch = getchar())) if(ch == '-') flag = 1;
		while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch - '0'), ch = getchar();
		if(flag) x = -x;
	}
	template<typename Tp , typename ...  Args>
	inline void read(Tp &x, Args & ... x_) {
		read(x);
		read(x_ ... );
	}
};
using namespace FastIO;

int n, m;
ll a[50][50];

ll dp[50][50];
ll B[50];

inline void Input() {
	read(n, m);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			read(a[i][j]);
		}
	}
}

inline void Work() {
	B[0] = 1;
	for(int i = 1; i <= m + 5; i++) {
		B[i] = B[i - 1] * 2;
	}
	ll ans = 0;
	for(int h = 1; h <= n; h++) {
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= m; i++) {
			for(int j = m; j >= i; j--) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j] + B[m - j + i - 1] * a[h][i - 1]);
				dp[i][j] = max(dp[i][j], dp[i][j + 1] + B[m - j + i - 1] * a[h][j + 1]);
			}
		}
		ll now = 0;
		for(int i = 1; i <= m; i++) {
			now = max(now, dp[i][i] + B[m] * a[h][i]);
		}
		ans += now;
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1; 
	// read(T);
	while(T--) {
		Input();
		Work();
	}
	return 0;
}