这道题大部分时间都在弄高精度……
还是先讲讲dp吧
这道题是一个区间dp，不过我还是第一次遇到这种类型的区间dp
f[i][j]表示取了数之后剩下i到j这个区间的最优值
注意这里是取了i之前和j之后的，i到j的数并没有取。
那么这个状态要不是取了第i-1个数转移而来，要不是取了第j+1个数转移而来。
所以可以写出方程 f[i][j] = max(f[i-1][j] + a[i-1] * mi[m-j+i-1], f[i][j+1] + a[j+1] * mi[m-j+i-1]);
然后注意这个区间dp是从大区间推到小区间，不一样。所以枚举的时候要注意区间是从大到小
ans = max(f[i][i] + mi[m])
然后这道题要用高精度。
注意不需要写高精*高精，可以写低精*高精
然后加法那里当前位数一定是+=，因为当前位数可能包含了进位
还要注意位数的调整
这里我弄了好久好久。我干脆趁这个机会搞个模板出来。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 112;
const int base = 10000;
struct node
{int len, s[505]; //s的范围开太大空间会炸 node() { len = 0; memset(s, 0, sizeof(s)); } void print(){printf("%d", s[len]); //注意第一位不用补0 for(int i = len - 1; i >= 1; i--) printf("%04d", s[i]);puts("");}}f[MAXN][MAXN], mi[MAXN];
int a[MAXN], n, m;node operator + (const node& a, const node& b)
{node c;int& len = c.len = max(a.len, b.len);_for(i, 1, len){c.s[i] += a.s[i] + b.s[i]; //这里一定是+=，不是= c.s[i+1] += c.s[i] / base;c.s[i] %= base;} if(c.s[len+1] > 0) c.len++;return c;
}node operator * (const int& a, const node& b)
{node c;int& len = c.len = b.len;_for(i, 1, b.len){c.s[i] += b.s[i] * a;c.s[i+1] += c.s[i] / base;c.s[i] %= base;}while(c.s[len+1] > 0) //进位是这么进位的 {c.len++;c.s[len+1] += c.s[len] / base;c.s[len] %= base;}return c;
}node max(node a, node b)
{if(a.len > b.len) return a;else if(a.len < b.len) return b;else{for(int i = a.len; i >= 1; i--){if(a.s[i] > b.s[i]) return a;else if(a.s[i] < b.s[i]) return b;}return a;}
}int main()
{mi[0].s[1] = 1; mi[0].len = 1;_for(i, 1, 80) mi[i] = 2 * mi[i-1];scanf("%d%d", &n, &m);node ans; _for(k, 1, n){memset(f, 0, sizeof(f));_for(i, 1, m) scanf("%d", &a[i]);_for(i, 1, m)for(int j = m; j >= i; j--)f[i][j] = max(f[i-1][j] + a[i-1] * mi[m-j+i-1], f[i][j+1] + a[j+1] * mi[m-j+i-1]);node maxt; //为0就直接初始化就好了 _for(i, 1, m)maxt = max(maxt, f[i][i] + a[i] * mi[m]);ans = ans + maxt;}ans.print();return 0;
}