P1005 矩阵取数

题目描述

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

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

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

输入输出格式

输入文件包括 n+1 行：

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

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

输出格式

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

输入输出样例

输入 #1

1
2
3
2 3
1 2 3
3 4 2

输出 #1

1
82

HINT

NOIP 2007 提高第三题。

数据范围：

60% 的数据满足：1≤n,m≤30，答案不超过 $10^{16}$。

100% 的数据满足：1≤n,m≤80，$0≤a_{ij}≤1000$。

区间dp, 题目是取的，逆着放就可以了。。

然后就是预处理出2的幂，保存起来，用高精！

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
75
76
77
78
79
80
81
82
83
84
85
const int MAX=100+10;
int n,m;
ll a[MAX][MAX];
struct bigint{
	const static int MOD=10000;
	int a[1000],len;
	bigint(){
		memset(a,0,sizeof(a));
		len = 1;
	} 
	bigint(ll x){
		memset(a,0,sizeof(a));
		len = 0;
		do{
			a[len++]=x%MOD;
			x/=MOD;
		}while(x);
	}
	bool operator < (const bigint &b) const{
		if(len<b.len) return true;
		if(len>b.len) return false;
		for(int i=len-1;i>=0;i--){
			if(a[i]<b.a[i]) return true;
			else if(a[i]>b.a[i]) return false;
		}
		return false;
	}
	bigint operator + (const bigint &b) const{
		bigint res;
		res.len=max(len,b.len);
		for(int i=0;i<res.len;i++){
			res.a[i]+=((i<len)?a[i]:0)+((i<b.len)?b.a[i]:0);
			res.a[i+1]+=res.a[i]/MOD;
			res.a[i]%=MOD;
		}
		if(res.a[res.len]>0) res.len++;
		return res;
	}
	bigint operator * (const bigint &b) const {
		bigint res;
		for(int i=0;i<len;i++){
			int up=0;
			for(int j=0;j<b.len;j++){
				int tmp=a[i]*b.a[j] + res.a[i+j]+up;
				res.a[i+j] = tmp % MOD;
				up = tmp / MOD;
			}
			if(up) res.a[i+b.len] = up;
		}
		res.len =len + b.len; 
		while(res.a[res.len -1] == 0 && res.len >1) res.len--;
		return res;
	}
	void print(){
		printf("%d",a[len-1]);
		for(int i=len-2;i>=0;i--){
			printf("%04d",a[i]);
		}
		puts("");
	}
};
bigint f[MAX][MAX],ans,p2[MAX];
int main(){
	freopen("in","r",stdin);
	p2[0]=bigint(1);
	fi(i,1,MAX) p2[i]=p2[i-1]*bigint(2);
	sf(n);sf(m);
	fi(i,0,n)
		fi(j,0,m) scanf("%lld",&a[i][j]);
	fi(i,0,n){
		fi(j,0,m) f[j][j]=bigint(a[i][j])*p2[m];
		fi(k,2,m+1){
			fi(j,0,m-k+1){ 
				int e = j + k - 1;
				bigint t1 = f[j+1][e] + bigint(a[i][j])*p2[m-k+1];
				bigint t2 = f[j][e-1] + bigint(a[i][e])*p2[m-k+1];
				if(t1<t2) f[j][e] = t2;
				else f[j][e] = t1;
			}
		}
		ans = ans + f[0][m-1];
	}
	ans.print();
	return 0;
}