题解 P1005 【矩阵取数游戏】

## 题目大意 > 有一个$n \times m$的矩阵，对于第$i$行，每次**取走**边缘的值$A_{i,j}$，增加这一行的得分$x$~~(自行看题目规则)~~，求$n$行的最大得分总和。 ## 分析一下 - 求$n$行最大得分和，每一行取数又不会影响到其他行，那么只要确保每一行得分最大，管好自家孩子就行了。（这个在动规中叫**最优子结构**） - 每次取数是在边缘取，那么每次取数完剩下来的元素一定是在一个完整的一个区间中，又是求最优解，**区间DP**应运而生。 ## DP流程 (每次DP仅针对第$T$行) ### 状态 - 我们用$f_{i,j}$表示区间**变为**$[i,j]$时，获得的最大分数。 ### 转移 - 当区间变为$[i,j]$时，上一次取数的时候区间一定是$[i-1,j]$或$[i,j+1]$，从这两个状态转移即可。在第$m-j+i-1$次(这个请自行模拟)取走了$A_{i-1,j}$或$A_{i,j+1}$即：$$f_{i,j}=max\{f_{i-1,j}+A_{i-1,j} \cdot 2^{m-j+i-1},f_{i,j+1}+A_{i,j+1} \cdot 2^{m-j+i-1}\}$$ ### 终值（答案） - 啊这个终值超级讨厌，状态不明确的话还真想不出来。 - 因为题目中说要取完，但是空区间是DP不出来的，然后就得手动模拟每个长度为$1$的区间。即： $$Ans=max_{i \leq m}\{f_{i,i}+A_{i,i} \cdot 2^m\}$$ ----- ## 一些~~(超级烦的)~~事情 - 我就不说为什么要用**高精度**了$\cdots$ - 啊高精度好烦的$\cdots$ - 烦归烦我又有什么办法呢，我又不会$int128 \cdots$ #### 总结一下要用的所有高精度 1. 高精$+$高精 2. 高精$\times$单精 3. $max\{$高精$,$高精$\}$(手动调皮) #### 好了我不管你们想粘板子就粘板子吧$\cdots$ ***** ## 代码君 ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; const int MAXN = 85, Mod = 10000; //高精四位压缩大法好 int n, m; int ar[MAXN]; struct HP { int p[505], len; HP() { memset(p, 0, sizeof p); len = 0; } //这是构造函数，用于直接创建一个高精度变量 void print() { printf("%d", p[len]); for (int i = len - 1; i > 0; i--) { if (p[i] == 0) { printf("0000"); continue; } for (int k = 10; k * p[i] < Mod; k *= 10) printf("0"); printf("%d", p[i]); } } //四位压缩的输出 } f[MAXN][MAXN], base[MAXN], ans; HP operator + (const HP &a, const HP &b) { HP c; c.len = max(a.len, b.len); int x = 0; for (int i = 1; i <= c.len; i++) { c.p[i] = a.p[i] + b.p[i] + x; x = c.p[i] / Mod; c.p[i] %= Mod; } if (x > 0) c.p[++c.len] = x; return c; } //高精+高精 HP operator * (const HP &a, const int &b) { HP c; c.len = a.len; int x = 0; for (int i = 1; i <= c.len; i++) { c.p[i] = a.p[i] * b + x; x = c.p[i] / Mod; c.p[i] %= Mod; } while (x > 0) c.p[++c.len] = x % Mod, x /= Mod; return c; } //高精*单精 HP max(const HP &a, const HP &b) { if (a.len > b.len) return a; else if (a.len < b.len) return b; for (int i = a.len; i > 0; i--) if (a.p[i] > b.p[i]) return a; else if (a.p[i] < b.p[i]) return b; return a; } //比较取最大值 void BaseTwo() { base[0].p[1] = 1, base[0].len = 1; for (int i = 1; i <= m + 2; i++){ //这里是m! m! m! 我TM写成n调了n年... base[i] = base[i - 1] * 2; } } //预处理出2的幂 int main(void) { scanf("%d%d", &n, &m); BaseTwo(); while (n--) { memset(f, 0, sizeof f); for (int i = 1; i <= m; i++) scanf("%d", &ar[i]); for (int i = 1; i <= m; i++) for (int j = m; j >= i; j--) { //因为终值是小区间，DP自然就从大区间开始 f[i][j] = max(f[i][j], f[i - 1][j] + base[m - j + i - 1] * ar[i - 1]); f[i][j] = max(f[i][j], f[i][j + 1] + base[m - j + i - 1] * ar[j + 1]); } //用结构体重载运算符写起来比较自然 HP Max; for (int i = 1; i <= m; i++) Max = max(Max, f[i][i] + base[m] * ar[i]); ans = ans + Max; //记录到总答案中 } ans.print(); //输出 return 0; } ```