P1005 矩阵取数游戏

区间dp，每一行单独处理，因为数据范围比较大所以要用高精或者__int128。
对于每行来说，用f[i,j]表示取完当前行的第i~j个数的最大值，则f[i,j]=max(f[i+1,j]+a[i]*2^(m-(i-j+1)),f[i,j+1]+a[j]*2^(m-(i-j+1))
初始化：f[i,i]=a[i]*2^m(最后一个)，目标：f[1,m]
打印时记得加特判ans=0

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cctype>
 5 #include <iostream>
 6 using namespace std;
 7 
 8 #define res register int
 9 inline int read()
10 {
11     int x(0),f(1); char ch;
12     while(!isdigit(ch=getchar()))  if(ch=='-') f=-1;
13     while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
14     return f*x;
15 }
16 
17 const int N=80+5;
18 int n,m;
19 __int128 f[N][N],ans,a[N],p[N];
20 
21 inline void print(__int128 x)
22 {
23     if(!x) return;
24     print(x/10);
25     putchar(x%10+'0');
26 }
27 
28 int main()
29 {
30     n=read(); m=read();
31     p[0]=1; 
32     for(res i=1 ; i<=m ; i++) p[i]=p[i-1]*2;
33     for(res i=1 ; i<=n ; i++)
34     {
35         memset(f,0,sizeof(f));
36         for(res j=1 ; j<=m ; j++) a[j]=read(),f[j][j]=a[j]*p[m];
37         for(res len=2 ; len<=m ; len++)
38         {
39             for(res l=1 ; l<=m-len+1 ; l++)
40             {
41                 int r=l+len-1;
42                 f[l][r]=max(f[l+1][r]+a[l]*p[m-len+1],f[l][r-1]+a[r]*p[m-len+1]);
43             }
44             ans+=f[1][m];
45         }
46     }
47     if(!ans) printf("0");
48     else print(ans);
49     return 0;
50 }

View Code