高精度真好van
假的
#include#include #include #include using namespace std;struct node//高精度结构体{ int len; int base[101]; void fill(int val)//初始化函数，每次写高精度，都感觉自己是一点点凑出来的233 { memset(base,0,sizeof(base)); len=0; if(!val) return ; while(val>=10000) { base[len++]=val%10000; val/=10000;//压一个小位 } len-=1; if(val) base[++len]=val; return ; } node operator + (const node &a)const//普通的加号 { node res; res.fill(0);//普通的调用 res.len=max(len,a.len); for(int i=0;i<=res.len;i++) { res.base[i]+=base[i]+a.base[i]; res.base[i+1]+=res.base[i]/10000; res.base[i]%=10000;//普通的压位 } if(res.base[len+1]) res.len+=1; while(!res.base[res.len]) res.len-=1;//普通且冗杂的调整尾数 if(res.len==-1) res.len=0; return res; } node operator * (const node &a)const { node res; res.fill(0); res.len=len+a.len; for(int i=0;i<=len;i++) for(int j=0;j<=a.len;j++) { res.base[i+j]+=base[i]*a.base[j]; res.base[i+j+1]+=res.base[i+j]/10000; res.base[i+j]%=10000; } if(res.base[res.len+1]) res.len+=1; while(!res.base[res.len]) res.len-=1; if(res.len==-1) res.len=0; return res; }};node max(const node &a,const node &b){ if(a.len!=b.len) return (a.len > b.len ? a : b ); for(int i=a.len;i>=0;i--) if(a.base[i]!=b.base[i]) return (a.base[i] > b.base[i] ? a : b); return a;//比较大小}node twi[81];int base[1010];node dp[90][90];node ans;node pas;node pas1,pas2;int main(){ twi[0].fill(1); twi[1].fill(2); for(int i=2;i<=80;i++) twi[i]=twi[i-1]*twi[1];//预处理2的幂 int n,m; scanf("%d%d",&n,&m); ans.fill(0); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) scanf("%d",&base[j]); pas.fill(base[1]);dp[1][0]=pas*twi[1]; pas.fill(base[m]);dp[0][1]=pas*twi[1]; for(int k=2;k<=m;k++) for(int j=0;j<=k;j++) { pas1.fill(base[m-(k-j)+1]); pas2.fill(base[j]); dp[j][k-j].fill(0); if(k-j-1>=0) dp[j][k-j]=max(dp[j][k-j-1]+pas1*twi[k],dp[j][k-j]); if(j-1>=0) dp[j][k-j]=max(dp[j-1][k-j]+pas2*twi[k],dp[j][k-j]);//简单的dp } pas.fill(0); for(int j=0;j<=m;j++) pas=max(pas,dp[j][m-j]); ans=ans+pas; } printf("%d",ans.base[ans.len]); for(int i=ans.len-1;i>=0;i--) printf("%04d",ans.base[i]);//一定要补位！！！ return 0;}