P1005 [NOIP2007 提高组] 矩阵取数游戏 题解

题目

这个题是一道高精度加上区间动规的题，题不难，但是码量有亿点多。

将整个矩阵分成多个数列来处理，因为两个数列之间的取数关系互不干扰。

我们设 $d{p}_{ij}$ 为矩阵还剩从 $i$ 到 $j$ 部分时的最大和，轻松推出转移方程：
$$d{p}_{ij}=\max (d{p}_{ij},d{p}_{i-1j}+2^{m-j+i-1}\times a_{i-1},d{p}_{ij+1}+2^{m-j+i-1}\times aj+1)$$

然后从外部扩展到内部就可以了。

Attention!

这里我们无法得到剩下区间没有的情况，只能从 $d{p}_{kk}$ 的情况在转移到答案。

关于高精，我推荐写成结构体加上重载运算符加上压位，你不会压位？

AC Code：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<list>
#include<set>
#include<map>
using namespace std;
const int base = 10000;
int n, m;
int a[100];
struct hi_pres{
	int len, nums[110];
	hi_pres() {
		memset(nums, 0, sizeof(nums));
		len = 0;
	}
};
hi_pres ans, pow_2[1000], dp[100][100];
int getlen(const hi_pres &a) {
	for (int i = 100; i >= 0; i --) {
		if (a.nums[i]) {
			return i;
		}
	}
	return 0;
}
hi_pres operator + (const hi_pres &a, const hi_pres &b) {
	int la = getlen(a);
	int lb = getlen(b);
	hi_pres c;
	for (int i = 1; i <= max(la, lb); i ++) {
		c.nums[i] += a.nums[i] + b.nums[i];
		c.nums[i + 1] += c.nums[i] / base;
		c.nums[i] %= base;
	}
	getlen(c);
	return c;
}
hi_pres operator * (const hi_pres &a, const int &b) {
	int la = getlen(a);
	hi_pres c;
	for (int i = 1; i <= la; i ++) {
		c.nums[i] += a.nums[i] * b;
		c.nums[i + 1] += c.nums[i] / base;
		c.nums[i] %= base;
	}
	getlen(c);
	return c;
}
hi_pres max(const hi_pres &a, const hi_pres &b) {
	int la = getlen(a), lb = getlen(b);
	if (la > lb) return a;
	if (la < lb) return b;
	for (int i = la; i >= 1; i --) {
		if (a.nums[i] > b.nums[i]) return a;
		if (a.nums[i] < b.nums[i]) return b;
	}
	return a;
}
void print(const hi_pres a) {
	int la = getlen(a);
	printf("%d", a.nums[la]);
	for (int i = la - 1; i >= 1; i --) {
		if (a.nums[i] == 0) printf("0000");
		else if (a.nums[i] < 10) printf("000%d", a.nums[i]);
		else if (a.nums[i] < 100) printf("00%d", a.nums[i]);
		else if (a.nums[i] < 1000) printf("0%d", a.nums[i]);
		else printf("%d", a.nums[i]);
	}
}
int main(){
	scanf("%d%d", &n, &m);
	pow_2[0].len = 1;
	pow_2[0].nums[1] = 1;
	for (int i = 1; i <= 100; i ++) {
		pow_2[i] = pow_2[i - 1] * 2;
	}
	for (int i = 1; i <= n; i ++) {
		memset(dp, 0, sizeof(dp));
		for (int j = 1; j <= m; j ++) {
			scanf("%d", &a[j]);
		}
		for (int k = 1; k <= m; k ++) {
			for (int l = m; l >= k; l --) {
				dp[k][l] = max(dp[k][l], dp[k - 1][l] + pow_2[m - l + k - 1] * a[k - 1]); 
				dp[k][l] = max(dp[k][l], dp[k][l + 1] + pow_2[m - l + k - 1] * a[l + 1]);
			}
		}
		hi_pres maxx;
		for (int k = 1; k <= m; k ++) {
			maxx = max(maxx, dp[k][k] + pow_2[m] * a[k]);
		}
		ans = ans + maxx;
	}
	print(ans);
	return 0;
}
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101