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

谢士广博客 02-27 阅读 66评论

题目

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

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

我们设 d p i j dp_{ij} dpij 为矩阵还剩从 i i i 到 j j j 部分时的最大和，轻松推出转移方程： d p i j = max ⁡ ( d p i j , d p i − 1 j + 2 m − j + i − 1 × a i − 1 , d p i j + 1 + 2 m − j + i − 1 × a j + 1 ) dp_{ij} = max(dp_{ij}, dp_{i - 1 j} + 2 ^ {m - j + i - 1} imes a_{i - 1} , dp_{i j + 1} +2^{m-j+i-1} imes a{j +1}) dpij=max(dpij,dpi−1j+2m−j+i−1×ai−1,dpij+1+2m−j+i−1×aj+1)

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

Attention!

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

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

AC Code：

#include#include#include#include#include#include#include#include#include#includeusing 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;}