题面传送门：P1005 [NOIP2007 提高组] 矩阵取数游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
分析题目可知，这道题是一道求最值的问题，第一次看题没有认真读题，以为是每次只在某一行中选一个数，于是想了半天无果。重新读题才发现每次需要每行都取，那么这就很简单了，相当于在每一行中求一个最大取法，最后加起来即可，那么我们就想到了用dp来解决这个问题，我们每次可以取最前面或者最后面一个数，在这两种情况中取一个最大值，这样一直递归下去，最终就可以找到答案，可以得到dp[i][j] = max(dp[i-1][j]+base[m+i-j-1]*a[i-1]，dp[i][j+1]+base[m+i-j-1]*a[j+1])，其中base[i]代表2的i次方，a[i]代表当前取走的数，那么每行的最值怎么求呢？这就涉及到我们状态表示的问题了，我们dp[i][j]所表示的是当区间变为（i，j）时的最值，那么我们1枚举到m，dp[i][i]表示的状态就是取到最后一个数是i时的最大值，我们再将这个值加上a[i]*base[m]就是最终答案了，推到这里，这个题只解决了思路上的问题，我们一看数据范围，好家伙最大值为2^80*1000，也就是大约10^27，这是要用高精啊，那就写吧，通过dalao的题解，我学到了一种很高级的高精写法——四位压缩，这个写法的核心就是将常规高精的数组单个值存一位变为了存四位，dalao用结构体的一系列操作简单的实现了高精，其中用到了重载运算符，还让我学到了结构体自动初始化的写法，orz，具体实现我都在代码里注释出来了，详见：
#include<bits/stdc++.h> using namespace std; const int N = 85,Mod = 10000; int n,m,a[N]; //本题采用的是压四位的高精度计算，具体方法参见https://blog.csdn.net/q873040807/article/details/50519731/ struct node{ int p[505],len; node(){ memset(p,0,sizeof(p)); len = 0; }//这个函数可以实现自动初始化 void print(){//输出函数 printf("%d",p[len]); for(int i = len-1;i;i--){ if(p[i] == 0){//压四位输出法，orz printf("0000"); continue; } for(int k = 10;k * p[i] < Mod;k*=10){//判断每位是否为0，因为压四位，所以如果该位不为零，则乘以k后一定大于10000 printf("0"); } printf("%d",p[i]);//输出剩余值 } } }; node dp[N][N],base[N],ans; node operator + (const node &a,const node &b){ node 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; }//高精加高精 node operator * (const node &a,const int &b){ node 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){ c.p[++c.len] = x % Mod; x/=Mod; } return c; }//高精乘低精 node max(const node &a,const node &b){ if(a.len > b.len) return a; if(b.len > a.len) return b; for(int i = a.len;i;i--){ if(a.p[i]>b.p[i]){ return a; }else if(b.p[i]>a.p[i]){ return b; } } return a; }//重载max函数 void reeset(){ base[0].p[1] = 1; base[0].len = 1; for(int i = 1;i <= m+2;i++){ base[i] = base[i-1]*2; } }//初始化存储2的i次方 int main(){ scanf("%d%d",&n,&m); reeset(); for(int k = 1;k <= n;k++){ memset(dp,0,sizeof(dp)); for(int i = 1;i <= m;i++) scanf("%d",&a[i]); 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]+base[m+i-j-1]*a[i-1]); dp[i][j] = max(dp[i][j],dp[i][j+1]+base[m+i-j-1]*a[j+1]); } } node maxx; for(int i = 1;i <= m;i++){ maxx = max(maxx,dp[i][i]+base[m]*a[i]); } ans = ans + maxx; } ans.print(); return 0; }