【提高组NOIP2007】矩阵取数游戏 dp

题目描述
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素a[i,j] 均为非负整数。游戏规则如下：
每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
每次取走的各个元素只能是该元素所在行的行首或行尾；
每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2^i，其中i表示第i次取数（从1开始编号）；
游戏结束总得分为m次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入
输入文件game.in包括n+1行：

第1行为两个用空格隔开的整数n和m。第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。

输出
输出文件game.out仅包含1行，为一个整数，即输入矩阵取数后的最大得分。
样例输入
Sample Input1:
2 3
1 2 3
3 4 2
Sample Input2:
1 4
4 5 0 5
Sample Input3：
2 10
96 56 54 46 86 12 23 88 80 43
【【提高组NOIP2007】矩阵取数游戏】16 95 18 29 30 53 88 83 64 67
样例输出
Sample Output1:
82
【输入输出样例1解释】
第1次：第1行取行首元素，第2行取行尾元素，本次得分为1*21+2*21=6
第2次：两行均取行首元素，本次得分为2*22+3*22=20
第3次：得分为3*23+4*23=56。总得分为6+20+56=82
Sample Output2:
122
Sample Output3:
316994
数据范围限制
【限制】

60%的数据满足：1<=n, m<=30, 答案不超过10^16100%的数据满足：1<=n, m<=80, 0<=a[i,j]<=1000

思路：
dp
可以发现每一行可以单独处理，答案就是每一行获得的最大分数的和。

文章图片

要高精度，注意常数优化。

#include #pragma GCC optimize(3) #define open(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout); #define N 100 #define ll long long using namespace std; ll base=1000; ll work(ll b) { ll ans=0; while(b) { ans++; b/=10; } return ans; } struct bignum { ll len; ll num[100]; bignum(){len=1; memset(num,0,sizeof num); } void init(){len=1; memset(num,0,sizeof num); } bool operator < (const bignum &y) const { bignum x=*this; if(x.len < y.len) return 1; if(x.len > y.len) return 0; for(ll i=x.len; i>0; i--) if(x.num[i]>y.num[i]) return 0; else if(x.num[i]len=0; if(b==0) { this->len=1; return *this; } while(b) { this->num[++(this->len)]=b%base; b/=base; } return *this; } bignum operator +(const bignum b) { bignum &a=*this,c=bignum(); ll tmp=max(a.len,b.len); for(ll i=1; i<=tmp; i++)c.num[i]=a.num[i]+b.num[i]; for(ll i=1; i<=tmp; i++){c.num[i+1]+=c.num[i]/base; c.num[i]%=base; } if(c.num[tmp+1]>0)c.len=tmp+1; else c.len=tmp; return c; } bignum operator *(const ll a) { ll tmp=0; bignum b=*this; for(ll i=1; i<=b.len; i++)b.num[i]*=a; for(ll i=1; i<=b.len+3; i++) {b.num[i+1]+=b.num[i]/base; b.num[i]%=base; } if(b.num[b.len+3])b.len+=3; else if(b.num[b.len+2])b.len+=2; else if(b.num[b.len+1])b.len+=1; return b; } void print() { bignum a=*this; ll count=work(base)-1,temp=0; for(ll i=a.len; i>0; i--) { temp=work(a.num[i]); if(i!=a.len)while(temp++0) head=f[i-1][j-1]+make(a[j],i); f[i][j]=max(head,tail); } } }int main() { open("game"); scanf("%lld%lld",&n,&m); g[0].num[1]=1; for(i=1; i<=m; i++)g[i]=g[i-1]*2; for(i=1; i<=n; i++)for(j=1; j<=m; j++)scanf("%lld",&a[i][j]); for(i=1; i<=n; i++) { dp(a[i]); t.init(); for(j=0; j<=m; j++)t=max(t,f[m][j]); ans=ans+t; } ans.print(); }