题解 P1005 【矩阵取数游戏】

「QQ红包」

2017-09-10 00:18:37

Solution

一行一行的处理,最后加起来 f[i][j]表示取i~j这一段能获得的最大分数(i~j这部分最后取) 初始化:$f[i][i]=a[i]*2^m$ 转移方程: $$f[i][j]=max(f[i+1][j])+a[k][i]*2^{m+i-j},f[i][j-1]+a[k][j]*2^{m+i-j})$$ ```cpp #include<bits/stdc++.h> using namespace std; int n,m,lc; char ch[100]; int d[100]; int a[100][100][100]; int er[81][100]; int A[100]; int B[100]; int ans[200]; int f[81][81][100]; inline void Add(int *b,int *c)//b=b+c { memset(d,0,sizeof(d)); d[0]=max(b[0],c[0])+1; for (int I=1;I<=d[0];I++)//加法 { d[I]+=b[I]+c[I]; d[I+1]+=(d[I]/10); d[I]%=10; } while (d[d[0]]==0) d[0]--;//去掉0 for (int I=0;I<=d[0];I++) b[I]=d[I]; return; } inline void CF(int *b,int *c)//高精度乘法 { memset(d,0,sizeof(d));//清空 d[0]=b[0]+c[0]; for (int k=1;k<=b[0];k++)//乘 for (int l=1;l<=c[0];l++) { d[k+l-1]+=b[k]*c[l]; } for (int k=1;k<=d[0];k++)//进位 { d[k+1]+=d[k]/10; d[k]%=10; } while (d[d[0]]==0) d[0]--;//去掉前面的0 for (int k=0;k<=d[0];k++) b[k]=d[k]; } inline bool Max(int *b,int *c)//比较b数组和c数组哪个大 { while (b[b[0]]==0&&b[0]>0) b[0]--; while (c[c[0]]==0&&c[0]>0) c[0]--; if (b[0]>c[0]) return true; if (c[0]>b[0]) return false; for (int i=b[0];i>=1;i--) if (b[i]>c[i]) return true; else if (b[i]<c[i]) return false; return false; } bool flag; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { scanf("%s",ch+1);//读入 lc=strlen(ch+1); a[i][j][0]=0; for (int k=lc;k>=1;k--) { a[i][j][++a[i][j][0]]=ch[k]-'0'; } } er[0][0]=1;er[0][1]=1; for (int i=1;i<=m;i++)//预处理2^1~2^m { for (int j=0;j<=er[i-1][0];j++) { er[i][j]=er[i-1][j]; } Add(er[i],er[i-1]); } for (int k=1;k<=n;k++)//行 { memset(f,0,sizeof(f)); for (int i=1;i<=m;i++) {//f[i][i]=a[k][i]*2^m; Add(f[i][i],a[k][i]); CF(f[i][i],er[m]); } for (int l=1;l<m;l++) { for (int i=1,j=i+l;j<=m;i++,j=i+l) {//这就是dp转移的过程 memset(A,0,sizeof(A)); Add(A,a[k][i]); CF(A,er[m+i-j]); Add(A,f[i+1][j]); memset(B,0,sizeof(B)); Add(B,a[k][j]); CF(B,er[m+i-j]); Add(B,f[i][j-1]); flag=Max(A,B); if (flag) { for (int l=0;l<=A[0];l++) f[i][j][l]=A[l]; } else { for (int l=0;l<=B[0];l++) f[i][j][l]=B[l]; } } } Add(ans,f[1][m]); } while (ans[ans[0]]==0&&ans[0]>0) ans[0]--;//去掉0 if (ans[0]==0) ans[0]++;//特判0 for (int i=ans[0];i>=1;i--)//倒着输出 printf("%d",ans[i]); return 0; } ```