UVa1366 Martian Mining

首先应该想到一点, 如果一段管道被中途截断了, 那么这段管道就是毫无意义的, 没了它答案也不会变差.

那么, 决策就可以看成每次修一条管道(从下到上或者从右到左), 状态可以定为每次考虑一个矩阵(顺序从小到大)

其次,很明显这个题满足最优子结构性质.

那么就不难写出方程了

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int MAXN = 5e2 + 20;
 7 inline int read()
 8 {
 9     int x = 0; char ch = getchar();
10     while(!isdigit(ch)) ch = getchar();
11     while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
12     return x;
13 }
14 int N, M;
15 int squ[MAXN][MAXN][2];
16 int f[MAXN][MAXN];
17 
18 int main()
19 {
20     while(cin>>N>>M, N)
21     {
22         memset(squ, 0, sizeof(squ));
23         for(int i = 1; i <= N; i++)
24             for(int j = 1; j <= M; j++)
25                 squ[i][j][0] = squ[i][j - 1][0] + read();
26 
27         for(int i = 1; i <= N; i++)
28             for(int j = 1; j <= M; j++)
29                 squ[i][j][1] = squ[i - 1][j][1] + read(); 
30             
31         memset(f, 0, sizeof(f));
32         for(int i = 1; i <= N; i++)
33             for(int j = 1; j <= M; j++)
34                 f[i][j] = max(f[i][j], max(f[i][j - 1] + squ[i][j][1], f[i - 1][j] + squ[i][j][0]));
35         cout<<f[N][M]<<endl;
36     }
37     return 0;
38 }
原文地址:https://www.cnblogs.com/wsmrxc/p/9258535.html