【区间DP】P1005 矩阵取数游戏

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <vector>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 #define lll __int128
 8 
 9 int n, m;
10 int a[85][85];
11 lll f[85][85];
12 lll ans = 0;
13 
14 int main()
15 {
16     cin >> n >> m;
17     for (int i = 1; i <= n; i++)
18         for (int j = 1; j <= m; j++)
19             cin >> a[i][j];
20     for (int i = 1; i <= n; i++)
21     {
22         memset(f, 0, sizeof(f));
23         for (int j = 0; j <= m; j++)
24             for (int k = 1; k + j <= m; k++)
25                 f[k][j + k] = max(2 * f[k + 1][j + k] + 2 * a[i][k], 2 * f[k][k + j - 1] + 2 * a[i][j + k]);
26         ans += f[1][m];
27     }
28     if(!ans) cout<<0;
29     else
30     {
31     vector<int>out;
32     while (ans)
33     {
34         out.push_back(ans % 10);
35         ans /= 10;
36     }
37     int i = out.size();
38     while (i--)
39     {
40         cout << out[i];
41     }
42     }
43 }