[文章目录]
Description
帅帅经常更同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij据为非负整数。游戏规则如下：
1. 每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素；
2. 每次取走的各个元素只能是该元素所在行的行首或行尾；
3. 每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分 = 被取走的元素值*2^i，其中i表示第i次取数（从1开始编号）；
4. 游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
简单的想到DP，由于状态一定是连续的一段区间，并且行与行之间没有影响，所以记录端点DP。
dp[i][j]=max(dp[i-1][j]+a[i-1]*bin[k],bin[i][j+1]+a[j+1]*bin[k])。k为取的顺序中的第几个。然后一看数据，尼玛，高精度（不过nm^2的算法不整高精度也是可惜了）
然后写了个高精度，开心。额，我在练习自定义运算符啊。。。真的。。。
加了很清真的output(){非常方便调试}和maxx(node)函数。开心 代码好像不丑了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,a[100],mod=100000;
struct node
{
int a[12];
int len;
node(){memset(a,0,sizeof(a));len=1;}
node operator + (node x)
{
node ret;
ret.len=max(len,x.len);
int t=0;
for(int i=1;i<=ret.len;i++)
{
ret.a[i]=(a[i]+x.a[i]+t)%mod;
t=(a[i]+x.a[i]+t)/mod;
}
while(t) ret.a[++ret.len]=t%mod,t/=mod;
return ret;
}
node operator *(int x)
{
node ret;
if(x==0) return ret;
ret.len=len;
int t=0;
for(int i=1;i<=len;i++)
{
ret.a[i]=(a[i]*x+t)%mod;
t=(a[i]*x+t)/mod;
}
while(t) ret.a[++ret.len]=t%mod,t/=mod;
return ret;//第一遍居然忘写了。玛丽有只小羊羔。。。有点小
}
node operator += (node x)
{
*this=*this+x;
return *this;
}
void maxx(node x)
{
if(x.len!=len){if(x.len>len) *this=x; return ;}
for(int i=len;i>0;i--)
if(x.a[i]!=a[i]){if(x.a[i]>a[i]) *this=x; return ;}
return ;
}
void output()
{
printf("%d",a[len]);
for(int i=len-1;i>0/* 不能直接放个 i ，因为有len-1<0的情况，或者改写初始化就好了*/;i--) printf("%05d",a[i]);
return ;
}
}dp[100][100],ans,sum,bin[90],empty;
int main()
{
cin>>n>>m;
bin[0].a[1]=1;
for(int i=1;i<=m;i++)
bin[i]=bin[i-1]*2;
while(n--)
{
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
for(int i=m-1;i;i--)
{
for(int l=1,r;l+i-1<=m;l++)
{
r=l+i-1;
dp[l][r]=empty;//初始化，嗯，长知识了。
if(l-1>=1) dp[l][r].maxx(dp[l-1][r]+bin[m-i]*a[l-1]);
if(r+1<=m) dp[l][r].maxx(dp[l][r+1]+bin[m-i]*a[r+1]);
}
}
ans=empty;//ans=node();虽然是初始化了，但是相当于重新开了一个结构体，MLE 啊
for(int i=1;i<=m;i++)
ans.maxx(dp[i][i]+bin[m]*a[i]);
sum+=ans;
}
sum.output();
return 0;
}