UVA 1366 九 Martian Mining

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6     int dp[505][505][3];
 7 int main()
 8 {
 9     int n,m;
10     int sumY[505][505],sumB[505][505];
11     int i,j,k,x,y;
12     while(scanf("%d %d",&n,&m)!=EOF && n!=0 && m!=0)
13     {
14         memset(sumY,0,sizeof(sumY));
15         memset(sumB,0,sizeof(sumB));
16         memset(dp,0,sizeof(dp));
17         for(i=1;i<=n;i++)
18         {
19             for(j=1;j<=m;j++)
20             {
21                 scanf("%d",&x);
22                 sumY[i][j]=sumY[i][j-1]+x;
23             }
24         }
25         for(i=1;i<=n;i++)
26         {
27             for(j=1;j<=m;j++)
28             {
29                 scanf("%d",&y);
30                 sumB[i][j]=sumB[i-1][j]+y;
31             }
32         }
33 
34         for(i=1;i<=n;i++)
35         {
36             for(j=1;j<=m;j++)
37             {
38                 dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j][2])+sumY[i][j];
39                 dp[i][j][2]=max(dp[i][j-1][1],dp[i][j-1][2])+sumB[i][j];
40             }
41         }
42         printf("%d\n",max(dp[i-1][j-1][1],dp[i-1][j-1][2]));
43     }
44     return 0;
45 }