关键字：高精度。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：
1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；
2.每次取走的各个元素只能是该元素所在行的行首或行尾；
3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值*2^i，其中i表示第i次取数（从1开始编号）；
4.游戏结束总得分为m次取数得分之和。
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
Input Format
第1行为两个用空格隔开的整数n和m。
第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。
Output Format
仅包含1行，为一个整数，即输入矩阵取数后的最大得分。
Sample Input #1
2 3
1 2 3
3 4 2
Sample Output #1
82
Hint
对于60%的数据，1<=n, m<=30，答案不超过10^16；
对于100%的数据，1<=n, m<=80，0<=aij<=1000.
比较容易的dp题，不过需要写高精度有点麻烦......对于每一行，我们令f(i,j)表示第i次取数后从左边取了j次数（j≤i），那么
f(i,j) =max(f(i-1,j)+num(m+1-(i-j))*2^i,f(i-1,j-1)+num(j)*2^i)（max里的第一个式子表示第i次从右边取，第二个式子表示从左边取，num(x)表示从左向右数第x个 数）。答案就是i=m时的最大值之和。
#include <cstdio>
#include <cstring>
#define MOD 10000
struct bigNum
{
int len,x[15];
bigNum()
{
memset(x,0,sizeof(x));
len = 1;
}
void print()
{
int i;
if(len == 1 && x[1] == 0) printf("0");
else
{
printf("%d",x[len]);
for(i=len-1;i;i--) printf("%.4d",x[i]);
}
}
void clear()
{
memset(x,0,sizeof(x));
len = 1;
}
}f[85][85],ans,tans;
bigNum max (bigNum a,bigNum b)
{
int i;
if(a.len != b.len) return a.len > b.len ? a : b;
for(i=a.len;i;i--) if(a.x[i] != b.x[i]) return a.x[i] > b.x[i] ? a : b;
return a;
}
bigNum operator + (bigNum a,bigNum b)
{
int i,t,lim = a.len>b.len?a.len:b.len;
bigNum c;
for(i=1;i<=lim+3;i++)
{
t = a.x[i]+b.x[i]+c.x[i];
c.x[i+1] += t/MOD;
c.x[i] = t%MOD;
}
for(i--;!c.x[i]&&i>1;i--);
c.len = i;
return c;
}
bigNum operator * (bigNum a,int b)
{
int i,t;
bigNum c;
for(i=1;i<=a.len+3;i++)
{
t = c.x[i]+a.x[i]*b;
c.x[i+1] += t/MOD;
c.x[i] = t%MOD;
}
for(i--;!c.x[i]&&i>1;i--);
c.len = i;
return c;
}
int n,m,num[85];
int main()
{
int i,j;
bigNum tmp;
scanf("%d%d",&n,&m);
while(n--)
{
for(i=1;i<=m;i++) scanf("%d",&num[i]);
tans.clear(); tmp.clear(); tmp.x[1] = 1;
for(i=1;i<=m;i++)
{
tmp = tmp*2;
for(j=0;j<=i;j++)
{
if(!j) f[i][0] = f[i-1][0]+tmp*num[m+1-i];
else if(j == i) f[i][i] = f[i-1][i-1]+tmp*num[i];
else f[i][j] = max(f[i-1][j]+tmp*num[m+1-(i-j)],f[i-1][j-1]+tmp*num[j]);
if(i == m) tans = max(tans,f[i][j]);
}
}
ans = ans + tans;
}
ans.print();
return 0;
}
评论 (0)
