题目链接：http://acm.ocrosoft.com/problem.php?cid=1630&pid=11
题目描述：帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的nXm的矩阵，矩阵中的每个元素a均
为非负整数。游戏规则如下
①每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有的元素
②每次取走的各个元素只能是该元素所在行的行首或行尾；
2、③每次取数都有一个得分值，为每行取数的得分之和；每行取数的得分＝被取走的元素值*(2^i)
其中i表示第i次取数（从1开始编号）
④游戏结東总得分为m次取数得分之和
帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。
输入
输入文件包括n＋1行
第一行为两个用空格隔开的整数n和m
第2-n+1行为N*M矩阵，其中每行m个用单个空格隔开
输出
输出文件仅包含一行，为一个整数，即输入矩阵去数后的最大得分
样例输入
2 3
1 2 3
3 4 2 样例输出
82 提示
60%的数据满足：1<=n, m<=30，答案不超过10^16
100%的数据满足：1<=n, m<=80，0<=aij<=1000
思路：每行之间的取数其实并不互相影响，所以只需求每行的最大分数，再将每行的最大分数加起来即可。这样问题就转换成了求每一行的最大分数。状态转移方程为maxi[k][j]=max(maxi[k][j-1]+a[i][j]*(ll)(pow(2,m-j+k)),maxi[k+1][j]+a[i][k]*(ll)(pow(2,m-j+k)));
也即只需判断比较是先取左边的结果较大还是先加右边的结果较大。
这是对于一般数据的AC代码:
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long long
int n,m;
ll sum = 0,maxi[105][105],a[105][105]={0};
ll max(ll x,ll y)
{
if(x>y)
return x;
else
return y;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
scanf("%lld",&a[i][j]);
}
for(int i = 1; i <= n; i++)
{
memset(maxi,0,sizeof(maxi));
for(int j = 1; j <= m; j++)
{
for(int k = 1; k <= m; k++)
{
if(j==k)
maxi[j][k]=(ll)(pow(2,m))*a[i][j];
}
}
for(int j = 2; j <= m;j++)
{
for(int k = j-1;k>0;k--)
{
maxi[k][j]=max(maxi[k][j-1]+a[i][j]*(ll)(pow(2,m-j+k)),maxi[k+1][j]+a[i][k]*(ll)(pow(2,m-j+k)));
}
for(int k = j+1; k <= m; k++)
{
maxi[j][k]=max(maxi[j][k-1]+a[i][k]*(ll)(pow(2,m+j-k)),maxi[j+1][k]+a[i][j]*(ll)(pow(2,m+j-k)));
}
}
sum+=maxi[1][m];
}
printf("%lld",sum);
return 0;
} 最重要的就是把这个代码改造成高精度。。
代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
int n=0,m=0;
int cifang[91][35];//此数组用于记录二的次方
int m1[35],m2[35];//此数组用于乘法的结果
int mm1[35],mm2[35];//此数组用于记录相加结果
int sum[45];//用于记录最后的结果。
int maxi[105][105][35];//用于动态转移
int a[105][105];
void chucifang()//初始化每个二的次方
{
cifang[1][30]=2;
for(int i = 2; i <= 80; i++)//根据题目要求初始化到2的m次方
{
for(int j = 30;j>0;j--)//题目数据2^80有二十多位。
cifang[i][j]=cifang[i-1][j]*2;
for(int j = 30; j>0;j--)
{
cifang[i][j-1]=cifang[i][j-1]+cifang[i][j]/10;
cifang[i][j]=cifang[i][j]%10;
}
}
return;
}
bool max()
{
for(int i = 0; i <= 30; i++)
{
if(mm1[i]>mm2[i])
return true;
if(mm1[i]<mm2[i])
return false;
}
return true;
}
void erchengshu1(int x,int y,int kk)
{
for(int j = 30; j > 0; j--)
{
m1[j]=a[x][y]*cifang[kk][j];
}
for(int j = 30; j > 0; j--)
{
m1[j-1]=m1[j-1]+m1[j]/10;
m1[j]=m1[j]%10;
}
return;
}
void jiluchu1(int x,int y)
{
for(int i = 1; i<=30;i++)
maxi[x][y][i]=m1[i];
return;
}
void jia1(int x,int y)
{
for(int i = 30; i>0;i--)
{
mm1[i]=m1[i]+maxi[x][y][i];
}
for(int i = 30; i>0;i--)
{
mm1[i-1]=mm1[i-1]+mm1[i]/10;
mm1[i]=mm1[i]%10;
}
return;
}
void jilu1(int x,int y)
{
for(int i = 1; i<=30;i++)
maxi[x][y][i]=mm1[i];
return;
}
void erchengshu2(int x,int y,int kk)
{
for(int j = 30; j > 0; j--)
{
m2[j]=a[x][y]*cifang[kk][j];
}
for(int j = 30; j > 0; j--)
{
m2[j-1]=m2[j-1]+m2[j]/10;
m2[j]=m2[j]%10;
}
return;
}
void jia2(int x,int y)
{
for(int i = 30; i>0;i--)
{
mm2[i]=m2[i]+maxi[x][y][i];
}
for(int i = 30; i>0;i--)
{
mm2[i-1]=mm2[i-1]+mm2[i]/10;
mm2[i]=mm2[i]%10;
}
return;
}
void jilu2(int x,int y)
{
for(int i = 1; i<=30;i++)
maxi[x][y][i]=mm2[i];
return;
}
/* for(int i = 10;i > 0;i--)
{
for(int j = 100; j > 0; j--)
{
m1[j+i-100]=m1[j+i-100]+zhongjian[i]*cifang[m][j];
}
for(int j = 100; j > 0; j--)
{
m1[j-1]=m1[j-1]+m1[j]/10;
m1[j]=m1[j]%10;
}
}*/
void sumjia()
{
for(int i = 30; i>0;i--)
{
sum[i+10]=sum[i+10]+maxi[1][m][i];
}
for(int i = 40; i>0;i--)
{
sum[i-1]=sum[i-1]+sum[i]/10;
sum[i]=sum[i]%10;
}
return;
}
int main()
{
memset(a,0,sizeof(a));
memset(sum,0,sizeof(sum));
memset(cifang,0,sizeof(cifang));
memset(m1,0,sizeof(m1));
memset(m2,0,sizeof(m2));
memset(mm1,0,sizeof(mm1));
memset(mm2,0,sizeof(mm2));
memset(maxi,0,sizeof(maxi));
scanf("%d %d",&n,&m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
scanf("%d",&a[i][j]);
}
chucifang();
for(int i = 1; i <= n; i++)//一共n排
{
for(int j = 1; j <= m; j++)//将只有
{
//将最后一个合并的人初始化
memset(m1,0,sizeof(m1));
erchengshu1(i,j,m);//进行大数乘法
jiluchu1(j,j);//记录所得结果
//maxi[j][j]=(ll)(pow(2,m))*a[i][j];
}
for(int j = 2; j <= m;j++)
{
for(int k = j-1;k>0;k--)
{
memset(m1,0,sizeof(m1));
memset(m2,0,sizeof(m2));
memset(mm1,0,sizeof(mm1));
memset(mm2,0,sizeof(mm2));
erchengshu1(i,j,m-j+k);
erchengshu2(i,k,m-j+k);
jia1(k,j-1);
jia2(k+1,j);
if(max()==true)//取mm1
jilu1(k,j);
else//取mm2
jilu2(k,j);
//maxi[k][j]=max(maxi[k][j-1]+a[i][j]*(ll)(pow(2,m-j+k)),maxi[k+1][j]+a[i][k]*(ll)(pow(2,m-j+k)));
}
for(int k = j+1; k <= m; k++)
{
memset(m1,0,sizeof(m1));
memset(m2,0,sizeof(m2));
memset(mm1,0,sizeof(mm1));
memset(mm2,0,sizeof(mm2));
erchengshu1(i,k,m+j-k);
erchengshu2(i,j,m+j-k);
jia1(j,k-1);
jia2(j+1,k);
if(max()==true)//取mm1
jilu1(j,k);
else//取mm2
jilu2(j,k);
//maxi[j][k]=max(maxi[j][k-1]+a[i][k]*(ll)(pow(2,m+j-k)),maxi[j+1][k]+a[i][j]*(ll)(pow(2,m+j-k)));
}
}
sumjia();//大数加法，负责将m行的最大值加入sum
//sum+=maxi[1][m];
}
//printf("%lld",sum);
int ggg=0,fla=0;
while(sum[ggg]==0&&ggg<41)
ggg++;
for(;ggg<=40; ggg++)
{
printf("%d",sum[ggg]);
fla=1;
}
if(fla==0)
printf("0\n");
return 0;
}
京公网安备 11010502036488号