https://www.luogu.org/problem/show?pid=1005
dp好想，高精度练手题，有点不舒服的是前后取数位置的计算，代码量太少才会写题这么慢，noip之前虽然重点放在知识点补全上但是基础还是要打扎实。
代码
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 int n,m; 9 struct mat{ 10 int e[50],len; 11 mat(){memset(e,0,sizeof(e));len=0;} 12 }; 13 int a[100][100]={}; 14 mat b2[100]={}; 15 mat f[100][100][2]; 16 mat mul(mat x,int y){ 17 mat z;z.len=x.len; 18 for(int i=1;i<=x.len;i++){ 19 z.e[i]+=x.e[i]*y; z.e[i+1]+=z.e[i]/10; 20 z.e[i]%=10; 21 if(z.e[i+1]!=0&&z.len==i){ 22 z.len++; 23 } 24 } 25 return z; 26 } 27 mat plu(mat x,mat y){ 28 mat z;z.len=max(x.len,y.len); 29 for(int i=1;i<=z.len;i++){ 30 z.e[i]+=x.e[i]+y.e[i]; 31 z.e[i+1]+=z.e[i]/10; 32 z.e[i]%=10; 33 if(z.e[i+1]!=0&&i==z.len){ 34 z.len++; 35 } 36 } 37 return z; 38 } 39 mat cham(mat x,mat y){ 40 if(x.len>y.len)return x; 41 if(x.len<y.len)return y; 42 for(int i=x.len;i>=1;i--){ 43 if(x.e[i]>y.e[i])return x; 44 if(x.e[i]<y.e[i])return y; 45 } 46 return x; 47 } 48 void put(mat x){ 49 if(x.len==0)printf("0"); 50 for(int i=x.len;i>=1;i--){ 51 printf("%d",x.e[i]); 52 } 53 printf(" "); 54 } 55 int main(){ 56 b2[0].e[1]=1;b2[0].len=1; 57 for(int i=1;i<=85;i++){ 58 b2[i]=mul(b2[i-1],2); 59 } 60 scanf("%d%d",&n,&m); 61 for(int i=1;i<=n;i++){ 62 for(int j=1;j<=m;j++){ 63 scanf("%d",&a[i][j]); 64 } 65 }mat z,z1,z2,z3,ans; 66 for(int i=1;i<=n;i++){ 67 for(int j=1;j<=m;j++){ 68 for(int w=1;w<=m;w++){ 69 if(w>j&&w<m-j+1)continue; 70 if(w<=j)f[j][w][0]=cham(f[j][w][0],cham(f[j-1][w-1][0],f[j-1][m-j+w+1][1])); 71 if(w>=m-j+1) f[j][w][1]=cham(f[j][w][1],cham(f[j-1][w+1][1],f[j-1][j-1-m+w][0])); 72 //put(f[j][w]); 73 f[j][w][1]=plu(f[j][w][1],mul(b2[j],a[i][w])); 74 f[j][w][0]=plu(f[j][w][0],mul(b2[j],a[i][w])); 75 } 76 } 77 z=z3; 78 for(int j=1;j<=m;j++){ 79 z=cham(z,f[m][j][0]); 80 z=cham(z,f[m][j][1]); 81 } 82 for(int j=1;j<=m;j++){ 83 for(int w=1;w<=m;w++){ 84 f[j][w][1]=z3; 85 f[j][w][0]=z3; 86 } 87 } 88 ans=plu(ans,z); 89 }put(ans); 90 return 0; 91 }