P1005 矩阵取数游戏

P1005 矩阵取数游戏
区间dp，憨贪心可以过两个点，
f[l][r]表示l,r这一段都选完的取得的最大得分
f[l][r]=max(f[1+l][r]+a[l],f[l][r-1]+a[r])*2
越靠中间，乘的2越多，枚举区间长度，和左右端点
答案是f[1][m]

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<ctime>
 7 #include<cstring>
 8 #define inf 2147483647
 9 #define For(i,a,b) for(register __int128 i=a;i<=b;i++)
10 #define p(a) putchar(a)
11 #define g() getchar()
12 //by war
13 //2017.10.19
14 using namespace std;
15 __int128 n,m;
16 __int128 a[100];
17 __int128 f[110][110];
18 __int128 Max;
19 __int128 ans;
20 void in(__int128 &x)
21 {
22     __int128 y=1;
23     char c=g();x=0;
24     while(c<'0'||c>'9')
25     {
26     if(c=='-')
27     y=-1;
28     c=g();
29     }
30     while(c<='9'&&c>='0')x=x*10+c-'0',c=g();
31     x*=y;
32 }
33 void o(__int128 x)
34 {
35     if(x<0)
36     {
37         p('-');
38         x=-x;
39     }
40     if(x>9)o(x/10);
41     p(x%10+'0');
42 }
43 int main()
44 {
45     in(n),in(m);
46     For(ii,1,n)
47      {
48          For(jj,1,m)
49          in(a[jj]);
50          For(i,1,m)
51          f[i][i]=2*a[i];
52        For(l,1,m-1)
53           For(i,1,m-l)
54               f[i][i+l]=max(f[i+1][i+l]+a[i],f[i][i+l-1]+a[i+l])*2;
55         ans+=f[1][m];
56         memset(f,0,sizeof(f));
57      }
58      o(ans);
59      return 0;
60 }

View Code