帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的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行，为一个整数，即输入矩阵取数后的最大得分。
2 3
1 2 3
3 4 2
82
NOIP 2007 提高第三题
Solution
简单的dp,高精好麻烦，不知道为什么跑得特别特别慢
大整数赋值的时候，要记得清0
重载的时候大于号和小于号不一样
哪位大佬告诉我为什么跑得这么慢
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int nn=83;
int n,m,a[nn];
struct bn{
int len,v[32];
bn(){len=0;memset(v,0,sizeof(v));}
bool operator <(const bn &x)const { //<>分开重载
if(len!=x.len)
return len<x.len;
for(int i=len;i>=1;i--)
if(v[i]!=x.v[i])
return v[i]<x.v[i];
return 0;
}
bn& operator*(bn x) {
bn res;
res.len=len+x.len;
for(int i=1;i<=len;i++)
for(int j=1;j<=x.len;j++)
{
res.v[i+j-1]+=v[i]*x.v[j];
res.v[i+j]+=res.v[i+j-1]/10;
res.v[i+j-1]=res.v[i+j-1]%10;
}
while(res.len>1&&!res.v[res.len]) res.len--;
return res;
}
bn& operator=(int x) {
len=0; ////////////////
memset(v,0,sizeof(v)); /////////////
while(x)
{
v[++len]=x%10;
x/=10;
}
len=len==0? 1:len;
return *this;
}
bn& operator=(bn x) {
len=x.len;
for(int i=1;i<=31;i++)
v[i]=x.v[i];
return *this;
}
bn& operator+(bn x){
bn res;
res.len=max(len,x.len)+1;
for(int i=1;i<=res.len;i++)
{
res.v[i]+=v[i]+x.v[i];
res.v[i+1]+=res.v[i]/10;
res.v[i]%=10;
}
while(res.len>1&&!res.v[res.len]) res.len--;
return res;
}
}two,dp[nn][nn],mi[nn];
inline int read()
{
register int ans=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch==‘-‘) f=-1;ch=getchar();}
while(isdigit(ch)) {ans=ans*10+ch-‘0‘;ch=getchar();}
return ans*f;
}
bn solve(int h)
{
bn ans,zc,ta;
for(register int i=1;i<=m;++i)
for(register int j=i;j<=m;++j)
dp[i][j]=0;
// memset(dp,0,sizeof(dp));
for(register int i=m-1;i>=1;--i)
for(register int j=1;j<=m-i+1;++j)
{
if(j-1>=1)
{
ta=a[j-1];
zc=dp[j-1][j+i-1]+ta*mi[m-i];
if(dp[j][j+i-1]<zc)
dp[j][j+i-1]=zc;
}
if(j+i<=m)
{
ta=a[i+j];
zc=dp[j][i+j]+ta*mi[m-i];
if(dp[j][i+j-1]<zc)
dp[j][j+i-1]=zc;
}
}
for(register int i=1;i<=m;++i)
{
ta=a[i];
dp[i][i]=dp[i][i]+ta*mi[m];
if(ans<dp[i][i])
ans=dp[i][i];
}
return ans;
}
int main()
{
two=2;
bn res;
n=read();m=read();
mi[0]=1;
for(register int i=1;i<=m;++i)
mi[i]=mi[i-1]*two;
for(register int i=1;i<=n;++i)
{
for(register int j=1;j<=m;++j)
a[j]=read();
res=res+solve(i);
}
for(register int i=res.len;i>=1;--i)
putchar(res.v[i]+‘0‘);
return 0;
}
原文：http://www.cnblogs.com/charlotte-o/p/7683911.html