[NOIP2017] 矩阵取数游戏

  • 本来是很简单的区间 DP
  • 结果还要加一个高精。。。
  • int128 走起 ```cpp

    include

    define int __int128

    using namespace std;
    const int N=82;
    int n,m,tot;
    int a[N];
    int f[N][N];
    int two[100];

void rd(int & x){
x=0;
char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-‘0’,c=getchar();}
void pr(int x){if(x==0)return;
pr(x/10);
putchar(x%10+’0’);
}

signed main(){rd(n);
rd(m);//scanf(“%lld%lld”,&n,&m);
two[0]=1;
for(int i=1;i<=m;i++)two[i]=two[i-1]2;
for(int i=1;i<=n;i++){// 分行 DP
for(int j=1;j<=m;j++)rd(a[j]);//scanf(“%lld”,&a[j]);
f[1][m]=0;
for(int l=m-2;l>=0;l—){int cur=two[m-l-1];
f[1][1+l]=f[1][2+l]+cur
a[2+l];
f[m-l][m]=f[m-l-1][m]+cura[m-l-1];
for(int j=2;j+l<m;j++){int t1=f[j-1][j+l]+cur
a[j-1];
int t2=f[j][j+l+1]+cura[j+l+1];
f[j][j+l]=(t1>t2?t1:t2);
}
}
int ans=0,fin=two[m];
for(int i=1;i<=m;i++)ans=max(ans,f[i][i]+fin
a[i]);
tot+=ans;
}
if(tot==0)putchar(‘0’);
else pr(tot);
return 0;
}
```


  目录