light oj 1071 dp（吃金币升级版）

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 #define ll long long
 7 
 8 using namespace std;
 9 const int N = 1e5+1000;
10 
11 int dp[105*2][105][105];
12 int maze[105][105];
13 
14 
15 int dfs(int sum,int a,int b)
16 {
17     if(dp[sum][a][b] != -1)
18         return dp[sum][a][b];
19     if(sum == 0 && a == 0 && b == 0)
20         return dp[sum][a][b] = maze[0][0];
21     dp[sum][a][b] = 0;
22     if(a == b)
23     {
24         if(sum - 1 >= 0)
25         dp[sum][a][b] = max(dp[sum][a][b],dfs(sum-1,a,b) + maze[a][sum-a]);
26         if(sum - 1 >= 0 && a - 1 >= 0)
27         dp[sum][a][b] = max(dp[sum][a][b],dfs(sum-1,a-1,b)+ maze[a][sum-a]);
28         if(sum - 1 >= 0 && b - 1 >= 0)
29         dp[sum][a][b] = max(dp[sum][a][b],dfs(sum-1,a,b-1) + maze[a][sum-a]);
30         if(sum - 1 >= 0 && a - 1 >= 0 && b - 1 >= 0)
31         dp[sum][a][b] = max(dp[sum][a][b],dfs(sum-1,a-1,b-1) + maze[a][sum-a]);
32     }
33     else
34     {
35         if(sum - 1 >= 0)
36         dp[sum][a][b] = max(dp[sum][a][b],dfs(sum-1,a,b) + maze[a][sum-a]+maze[b][sum-b]);
37         if(sum - 1 >= 0 && a - 1 >= 0)
38         dp[sum][a][b] = max(dp[sum][a][b],dfs(sum-1,a-1,b)+ maze[a][sum-a]+maze[b][sum-b]);
39         if(sum - 1 >= 0 && b - 1 >= 0)
40         dp[sum][a][b] = max(dp[sum][a][b],dfs(sum-1,a,b-1) + maze[a][sum-a]+maze[b][sum-b]);
41         if(sum - 1 >= 0 && a - 1 >= 0 && b - 1 >= 0)
42         dp[sum][a][b] = max(dp[sum][a][b],dfs(sum-1,a-1,b-1) + maze[a][sum-a]+maze[b][sum-b]);
43     }
44     return dp[sum][a][b];
45 }
46 
47 void solve()
48 {
49     int m,n;
50     scanf("%d %d",&m,&n);
51     memset(dp,-1,sizeof(dp));
52     memset(maze,0,sizeof(maze));
53     for(int i = 0; i < m; i++)
54         for(int j = 0; j < n; j++)
55         scanf("%d",&maze[i][j]);
56 
57     int ans = dfs(n+m-2,m-1,m-1);
58 
59     printf("%d
",ans);
60 }
61 
62 int main(void)
63 {
64     int t,cnt = 0;
65     scanf("%d",&t);
66 
67     while(t--)
68     {
69         printf("Case %d: ",++cnt);
70         solve();
71     }
72     return 0;
73 }