题目描述
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的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行，为一个整数，即输入矩阵取数后的最大得分。
输入输出样例
输入样例#1：
2 3 1 2 3 3 4 2
输出样例#1：
82
说明
NOIP 2007 提高第三题
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 100 6 using namespace std; 7 struct bigint{ 8 int a[maxn];//a[0]存位数 9 bigint(){memset(a,0,sizeof(a));} 10 11 bigint& operator=(const string s){//字符串类的赋值 12 int k=0; 13 for(int i=s.size()-1;i>=0;i--){ 14 k++; 15 this->a[k]=s[i]-'0'; 16 } 17 a[0]=s.size(); 18 return *this; 19 } 20 bigint& operator=(const int s){ 21 int num=s,i=0; 22 while(num){ 23 i++; 24 this->a[i]=num%10; 25 num/=10; 26 } 27 this->a[0]=i; 28 return *this; 29 } 30 31 32 /* bigint& operator=(const bigint &s){ 33 memset(a,0,sizeof(a)); 34 this->a[0]=s.a[0]; 35 for(int i=1;i<=s.a[0];i++){ 36 this->a[i]=s.a[i]; 37 } 38 return *this; 39 }*/ 40 //赋值部分结束 41 42 //运算符+ 43 bigint operator +(const bigint b){ 44 bigint c; 45 c.a[0]=max(a[0],b.a[0]); 46 for(int i=1;i<=c.a[0];i++){ 47 c.a[i]+=(a[i]+b.a[i]); 48 c.a[i+1]+=c.a[i]/10; 49 c.a[i]%=10; 50 } 51 if(c.a[c.a[0]+1]>0) 52 c.a[0]++; 53 return c; 54 } 55 56 //比较 57 /*bool operator <(const bigint b){ 58 if((this->a[0])!=b.a[0]) return (this->a[0])<b.a[0]; 59 for(int i=b.a[0];i>=1;i--){ 60 if((this->a[0])!=b.a[i]) 61 return (this->a[i])<b.a[i]; 62 } 63 return false; 64 }*/ 65 66 bool operator <(const bigint b){ 67 if(this->a[0]<b.a[0]) 68 return true; 69 if(this->a[0]>b.a[0]) 70 return false; 71 for(int i=b.a[0];i>=1;i--){ 72 if(this->a[i]!=b.a[i]) 73 return this->a[i]<b.a[i]; 74 } 75 return false; 76 } 77 bool operator >(bigint b){//不可写const,会报错 78 return b<(*this); 79 } 80 }; 81 82 ostream& operator<<(ostream&out,const bigint a){ 83 for(int i=a.a[0];i>=1;i--) 84 out<<a.a[i]; 85 return out; 86 } 87 istream& operator>>(istream&in,bigint& a){//不可写const 88 string s; 89 in>>s; 90 a=s; 91 return in; 92 } 93 94 int main(){ 95 int n,m; 96 cin>>m>>n; 97 bigint a[105]; 98 bigint tot,f[maxn][maxn]; 99 bigint q,p; 100 for(int num=1;num<=m;num++){ 101 for(int i=1;i<=n;i++) 102 cin>>a[i]; 103 for(int i=1;i<=n;i++)//预处理 104 f[i][i]=a[i]+a[i]; 105 106 for(int l=1;l<n;l++){ 107 for(int i=1;i<=n&&i+l<=n;i++){ 108 int j=i+l; 109 p=a[i]+f[i+1][j]; 110 q=a[j]+f[i][j-1]; 111 if(p<q) 112 f[i][j]=q+q; 113 else 114 f[i][j]=p+p; 115 } 116 } 117 tot=f[1][n]+tot; 118 memset(&a,0,sizeof(a));//注意& 119 memset(&f,0,sizeof(f)); 120 memset(&q,0,sizeof(q)); 121 memset(&p,0,sizeof(p)); 122 } 123 cout<<tot<<endl; 124 return 0; 125 }注释部分比较函数不可用，待查
就是一个struct版的高精度，抄自http://www.luogu.org/problem/lists
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！