题目描述
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2.每次取走的各个元素只能是该元素所在行的行首或行尾；
3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2^i，其中i表示第i次取数（从1开始编号）；
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。 输入输出格式 输入格式：
输入文件game.in包括n+1行：
第1行为两个用空格隔开的整数n和m。
第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。
数据范围：
60%的数据满足：1<=n, m<=30，答案不超过10^16
100%的数据满足：1<=n, m<=80，0<=aij<=1000
输出格式：
输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大得分。
动态规划，设dp[i][j]表示剩下i..j这一段的最大收益。
dp[i][j]=max{dp[i+1][j]+a[i] * 2^(m+i-j),dp[i][j+1]+a[i] * 2^(m+i-j)}
用到高精度。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=10000,maxn=80;
struct big
{int a[40],l;big operator + (const big & b){int i;big ret;ret.l=max(l,b.l);ret.a[1]=0;for (i=1;i<=ret.l;i++){ret.a[i]+=a[i]+b.a[i];ret.a[i+1]=ret.a[i]/mod;ret.a[i]%=mod;}if (ret.a[ret.l+1]) ret.l++;return ret;}big operator * (const big & b){int i,j;big ret;memset(ret.a,0,sizeof(ret.a));for (i=1;i<=l;i++)for (j=1;j<=b.l;j++){ret.a[i+j-1]+=a[i]*b.a[j];ret.a[i+j]+=ret.a[i+j-1]/mod;ret.a[i+j-1]%=mod;}ret.l=l+b.l-1;if (ret.a[ret.l+1]) ret.l++;return ret;}bool operator < (const big & b){int i;if (l!=b.l) return l<b.l;for (i=l;i;i--)if (a[i]!=b.a[i])return a[i]<b.a[i];return 0;}
}two,dp[85][85],pow[85],a[85],ans,t1,t2;
big gener(int x)
{big ret;memset(ret.a,0,sizeof(ret.a));ret.l=0;while (x){ret.l++;ret.a[ret.l]=x%mod;x/=mod;}return ret;
}
void out(big b)
{int i;printf("%d",b.a[b.l]);for (i=b.l-1;i>=1;i--){if (b.a[i]<1000) printf("0");if (b.a[i]<100) printf("0");if (b.a[i]<10) printf("0");printf("%d",b.a[i]);}printf("\n");
}
int m,n;
int main()
{int i,j,k,m,n,p,q,x,y,z,len;two=gener(2);pow[0]=gener(1);for (i=1;i<=maxn;i++)pow[i]=pow[i-1]*two;scanf("%d%d",&n,&m);ans=gener(0);while (n--){for (i=1;i<=m;i++){scanf("%d",&x);a[i]=gener(x);}for (i=1;i<=m;i++)dp[i][i]=a[i]*pow[m];for (len=2;len<=m;len++)for (i=1;(j=i+len-1)<=m;i++){t1=dp[i+1][j]+a[i]*pow[m-len+1];t2=dp[i][j-1]+a[j]*pow[m-len+1];if (t1<t2) dp[i][j]=t2;else dp[i][j]=t1;}ans=ans+dp[1][m];}out(ans);
}