1574: 矩阵取数游戏
时间限制: 1000 ms 内存限制: 524288 KB
题目描述
原题来自: NOIP 2007
帅帅经常和同学玩一个矩阵取数游戏: 对于给定的 n*m 的矩阵, 矩阵中每个元素 aij? 均为非负整数. 游戏规则如下:
每次取数时必须从每行各取走一个元素, 共
n 个,
m 次取完所有元素.
每次取走的各个元素只能是该元素所在行行首或行尾.
每次取数都有一个的分值, 为每行取数得分之和, 每行取数得分
=
= 被取走元素值
2^
i, 其中
i
i 表示第
i
次取数, 从
1 开始计数.
游戏结束时, 总得分为
m 次取数得分之和.
帅帅想让你帮忙写一个程序, 对于任意矩阵, 可以求出取数后的最大得分.
输入格式
输入包括 n+1 行. 第一行两个空格隔开的正整数 n,m 接下来 n 行每行 m 个用空格隔开的整数.
输出格式
输出为一个整数, 为所输入矩阵取数后的最大得分
样例
样例输入 1
2 3
1 2 3
3 4 2
样例输出 1
82
样例解释 1
第一次: 第一行取行首元素, 第二行取行尾元素, 本次得分为 1*2^1+2*2^1=6;
第二次: 两行均取行首元素, 本次得分为 2*2^2+3*2^2=20;
第三次: 本次得分为 3*2^3+4*2^3=56, 总得分为 6+20+56=826+20+56=82.
样例输入 2
1 4
4 5 0 5
样例输出 2
122
样例输入 3
- 2 10
- 96 56 54 46 86 12 23 88 80 43
- 16 95 18 29 30 53 88 83 64 67
样例输出 3
316994
数据范围与提示
对于 60% 的数据, 1≤n,m≤30, 答案不超过 10^16;
对于 100% 的数据, 1≤n,m≤80,0≤ai,j?≤1000.
sol: 区间 dp, 被高精恶心到了
- #include <bits/stdc++.h>
- using namespace std;
- const int N=85;
- const int L=105,Power=4,Base=10000;
- int n,m,a[N];
- struct Bignum
- {
- int a[L];
- Bignum(){memset(a,0,sizeof a);}
- Bignum(int x)
- {
- memset(a,0,sizeof a);
- while(x) {a[++*a]=x%10; x/=10;}
- return;
- }
- inline void Print()
- {
- int i;
- printf("%d",a[*a]);
- for(i=*a-1;i>=1;i--)
- {
- if(a[i]<1000) putchar('0');
- if(a[i]<100) putchar('0');
- if(a[i]<10) putchar('0');
- printf("%d",a[i]);
- }
- puts("");
- return;
- }
- inline void Init()
- {
- memset(a,0,sizeof a);
- }
- }Bin[N],dp[N][N];
- inline bool operator<(const Bignum &p,const Bignum &q)
- {
- if(p.a[0]!=q.a[0]) return (p.a[0]<q.a[0])?1:0;
- int i;
- for(i=p.a[0];i>=1;i--) if(p.a[i]!=q.a[i])
- {
- return (p.a[i]<q.a[i])?1:0;
- }
- return 0;
- }
- inline Bignum max(Bignum p,Bignum q)
- {
- return (p<q)?(q):(p);
- }
- inline Bignum operator+(const Bignum &p,const Bignum &q)
- {
- int i;
- Bignum ans=p;
- for(i=1;i<=q.a[0];i++)
- {
- ans.a[i]+=q.a[i];
- if(ans.a[i]>=Base){ans.a[i+1]+=ans.a[i]/Base; ans.a[i]%=Base;}
- }
- while(ans.a[ans.a[0]+1]) ans.a[0]++;
- return ans;
- }
- inline Bignum operator*(const Bignum &p,const Bignum &q)
- {
- int i,j;
- Bignum ans;
- ans.a[0]=p.a[0]+q.a[0];
- for(i=1;i<=p.a[0];i++)
- {
- for(j=1;j<=q.a[0];j++)
- {
- ans.a[i+j-1]+=p.a[i]*q.a[j];
- if(ans.a[i+j-1]>Base)
- {
- ans.a[i+j]+=ans.a[i+j-1]/Base;
- ans.a[i+j-1]%=Base;
- }
- }
- }
- while(!ans.a[ans.a[0]]) ans.a[0]--;
- return ans;
- }
- inline Bignum operator*(const Bignum &p,const int &q)
- {
- int i;
- Bignum ans;
- ans.a[0]=p.a[0]+5;
- for(i=1;i<=p.a[0];i++)
- {
- ans.a[i]+=p.a[i]*q;
- if(ans.a[i]>Base)
- {
- ans.a[i+1]+=ans.a[i]/Base; ans.a[i]%=Base;
- }
- }
- while(!ans.a[ans.a[0]]) ans.a[0]--;
- return ans;
- }
- inline Bignum Solve()
- {
- int i,j;
- for(i=1;i<=m;i++)
- {
- for(j=1;j+i-1<=m;j++)
- {
- int l=j,r=j+i-1;
- dp[l][r]=max(dp[l][r-1]+Bin[m-i+1]*a[r],dp[l+1][r]+Bin[m-i+1]*a[l]);
- }
- }
- // dp[1][m].Print();
- return dp[1][m];
- }
- int main()
- {
- int i,j;
- Bignum ans;
- scanf("%d%d",&n,&m);
- Bin[0]=Bignum(1);
- for(i=1;i<=m;i++) Bin[i]=Bin[i-1]*2;
- // for(i=1;i<=m;i++)
- // {
- // Bin[i].Print();
- // }
- // puts("");
- for(i=1;i<=n;i++)
- {
- for(j=1;j<=m;j++) scanf("%d",&a[j]);
- ans=ans+Solve();
- }
- ans.Print();
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2946770.html