题解 P1005 【矩阵取数游戏】

~~让我来一波50行精简代码的手写int128；~~ ------------ 首先推出状态转移方程 设 ``` f[l][l+len][i] ``` 表示左端点为l，右端点为l+len,第i行取数所能获得的最大值 很容易得出 ``` f[l][l+len][i]=max(2*f[l+1][l+len][i]+2*a[i][l],2*f[l][l+len-1][i]+2*a[i][l+len]); ``` 进一步推得 ``` f[l][l+len][i]=max(f[l+1][l+len][i]+a[i][l],f[l][l+len-1][i]+a[i][l+len])*2 ``` **如此化简方便重载运算符时减少运算量** ~~找八阿哥（bug）也方便一点~~ ------------ 目测发现最大数为**80x1000x(2^81-1)** 显然不会超过128位，于是我选择手写int128 用a.hig储存a的高位，a.low储存a的低位。 高位显然不会溢出（因为只有2^81-1），所以将低位的1e18空出，防止两数相加时溢出 ~~虽然这样一搞变成了int123 =_=~~ 输出时要格外注意： - 当高位为零时直接输出低位； - 当高位不为零时直接输出高位，低位位数不足18位要补零 - ~~当初就是因为低位没补零，找了八百十个小时的八阿哥~~ ------------ 代码（有注释）如下： ``` #include<cstdio> struct int128 { long long hig; long long low; };//定义int128 int n,m; long long p=1e18;//作mod用 int128 ans,f[85][85][85],a[85][85]; int128 max(int128 a,int128 b) { if(a.hig>b.hig) return a; if(a.hig<b.hig) return b;//高位比较 if(a.low>b.low) return a; if(a.low<b.low) return b;//低位比较 return a;//相等时还要返回一个值 } int128 operator + (int128 a,int128 b)//重载运算符 { int128 k; k.low=0,k.hig=0; k.low=a.low+b.low; k.hig=k.low/p+a.hig+b.hig;//防止溢出 k.low%=p; return k; } int128 operator * (int128 a,int b) { int128 k; k.low=0,k.hig=0; k.low=a.low*b; k.hig+=k.low/p+b*a.hig;//与上同理 k.low%=p; return k; } 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].low); for(int i=1;i<=n;i++) for(int len=0;len<m;len++) for(int l=1;l+len<=m;l++)//区间动态规划 f[l][l+len][i]=max(f[l+1][l+len][i]+a[i][l],f[l][l+len-1][i]+a[i][l+len])*2; for(int i=1;i<=n;i++) ans=ans+f[1][m][i]; if(ans.hig==0) printf("%lld",ans.low); else printf("%lld%018lld\n",ans.hig,ans.low); } ``` 纯代码： ``` #include<cstdio> struct int128 { long long hig; long long low; }; int n,m; long long p=1e18; int128 ans,f[85][85][85],a[85][85]; int128 max(int128 a,int128 b) { if(a.hig>b.hig) return a; if(a.hig<b.hig) return b; if(a.low>b.low) return a; if(a.low<b.low) return b; return a; } int128 operator + (int128 a,int128 b) { int128 k; k.low=0,k.hig=0; k.low=a.low+b.low; k.hig=k.low/p+a.hig+b.hig; k.low%=p; return k; } int128 operator * (int128 a,int b) { int128 k; k.low=0,k.hig=0; k.low=a.low*b; k.hig+=k.low/p+b*a.hig; k.low%=p; return k; } 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].low); for(int i=1;i<=n;i++) for(int len=0;len<m;len++) for(int l=1;l+len<=m;l++) f[l][l+len][i]=max(f[l+1][l+len][i]+a[i][l],f[l][l+len-1][i]+a[i][l+len])*2; for(int i=1;i<=n;i++) ans=ans+f[1][m][i]; if(ans.hig==0) printf("%lld",ans.low); else printf("%lld%018lld\n",ans.hig,ans.low); } ```