2016-05-31 17:26:45
题目链接: NOIP 2007 矩阵取数游戏(Codevs)
题目大意:
给定一个矩阵,每次在每一行的行首或者行尾取一个数乘上2^次数,求取完最多获得的分数
解法:
动态规划
DP[i][j]表示当前行i位置到j位置获得的最大分数
转移方程:
DP[i][j]=max(DP[i+1][j]+a[i]*2^x,DP[i][j-1]+a[i]*2^x);
需要注意的地方:
1.M和N给的范围略坑啊,2^80只有悄悄不说话了,所以直接上了100000的压位,感觉比高精好使多了
2.2的次方多次用到,所以预先处理出来待用
//矩阵取数游戏 (NOIP2007)
//动态规划 高精度
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=;
const int maxm=;
const int maxl=;
int N,M;
int a[maxn];
int DP[maxn][maxm][maxl];
int ys[maxn][maxl];
int ans[maxl];
int tmp[maxl];
void Multi(int *x,int *y,int z)
{
memset(tmp,,sizeof(tmp));
tmp[]=y[];
for(int i=;i<=tmp[];i++)
{
tmp[i]=y[i]*z;
}
for(int i=;i<=tmp[];i++)
{
tmp[i+]+=tmp[i]/;
tmp[i]%=;
}
while(tmp[tmp[]+])
{
tmp[]++;
tmp[tmp[]+]+=tmp[tmp[]]/;
tmp[tmp[]]%=;
}
for(int i=;i<;i++)x[i]=tmp[i];
return ;
}
void Add(int *x,int *y,int *z)
{
memset(tmp,,sizeof(tmp));
if(y[]>z[])tmp[]=y[];
else tmp[]=z[];
for(int i=;i<=tmp[];i++)
{
tmp[i]=y[i]+z[i];
}
for(int i=;i<=tmp[];i++)
{
tmp[i+]+=tmp[i]/;
tmp[i]%=;
}
if(tmp[tmp[]+])tmp[]++;
for(int i=;i<;i++)x[i]=tmp[i];
return ;
}
bool Max(int *x,int *y)
{
if(x[]>y[])return ;
else if(y[]>x[])return ;
else
{
for(int i=x[];i>=;i--)
{
if(x[i]>y[i])return ;
else if(x[i]<y[i])return ;
}
}
return ;
}
int main()
{
scanf("%d %d",&N,&M);
ys[][]=;
ys[][]=;
for(int i=;i<=M;i++)
{
Multi(ys[i],ys[i-],);
}
ans[]=;ans[]=;
for(int i=;i<=N;i++)
{
for(int j=;j<=M;j++)
{
scanf("%d",&a[j]);
Multi(DP[j][j],ys[M],a[j]);
}
for(int k=;k<=M;k++)
{
for(int x=;x<=M-k+;x++)
{
int y=x+k-;
int xm[],ym[],cm[];
Multi(cm,ys[M-k+],a[x]);
Add(xm,cm,DP[x+][y]);
Multi(cm,ys[M-k+],a[y]);
Add(ym,cm,DP[x][y-]);
if(Max(xm,ym))
{
memcpy(DP[x][y],xm,sizeof(int)*);
}
else
{
memcpy(DP[x][y],ym,sizeof(int)*);
}
}
}
Add(ans,ans,DP[][M]);
}
printf("%d",ans[ans[]]);
for(int i=ans[]-;i>=;i--)
{
printf("%05d",ans[i]);
}
printf("\n");
return ;
}