牛客练习赛21 B-黑妹的游戏二

题目链接：https://www.nowcoder.com/acm/contest/130/B

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=600;
 4 long long dp[maxn][maxn];
 5 int mp[maxn][maxn];
 6 
 7 int main()
 8 {
 9     int T;
10     scanf("%d",&T);
11     while(T--){
12         int n,m;
13         scanf("%d%d",&n,&m);
14         for(int i=1;i<=n;i++)
15             for(int j=1;j<=m;j++)
16                 scanf("%d",&mp[i][j]);
17         for(int i=n;i>0;i--){
18             for(int j=m;j>0;j--){
19                 long long tmp;
20                 if(i==n&&j==m) tmp=0;
21                 else if(i==n) tmp=dp[i][j+1];
22                 else if(j==m) tmp=dp[i+1][j];
23                 else tmp=max( dp[i][j+1], dp[i+1][j]);
24                 dp[i][j]=mp[i][j]-tmp;
25             }
26         }
27         printf("%lld
",dp[1][1]);
28     }
29     return 0;
30 }