首页 > 代码库 > lightoj1036_记忆化搜索

lightoj1036_记忆化搜索

http://lightoj.com/volume_showproblem.php?problem=1036

题意:给出一个n*m的地图,每个位置含有xi的金矿和yi的银矿。金矿都要运到地图的西边,银矿都要运到地图的南边。

每个位置可以建铁路,但是只能建东-西或者南-北中的一个,也就是所有铁路不能交叉,而且矿石不能倒车,也就是必须沿直线运到目的地。

求一种建铁路的方式使得最后得到的矿石最多?输出矿石数量。

思路:问题的本质在于,对于一个格子,要么是向左要么向上

(1)若一旦确定取该格子的矿金矿,则该格子左侧的都要取金矿;

(2)若一旦确定取该格子的矿银矿,则该格子上侧的都要取银矿;

看透这一步,就可以DP了。。。其实直接递推也挺简单的。。。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <ctime>
 8 #include <queue>
 9 #include <list>
10 #include <set>
11 #include <map>
12 using namespace std;
13 #define INF 0x3f3f3f3f
14 typedef long long LL;
15 
16 int a[510][510], b[510][510];
17 int dp[510][510];
18 struct node
19 {
20     int c;
21 }suma[510][510], sumb[550][550];
22 int dfs(int n, int m)
23 {
24     if(n == 1 && m == 1)
25         return max(a[1][1], b[1][1]);
26     if(n < 1 || m < 0)
27         return 0;
28     if(dp[n][m] != -1)
29         return dp[n][m];
30     int sum = 0;
31     sum = max(suma[n][m].c + dfs(n-1, m), sumb[n][m].c + dfs(n, m-1));
32     dp[n][m] = sum;
33     return sum;
34 }
35 int main()
36 {
37     int t, n, m;
38     scanf("%d", &t);
39     for(int ca = 1; ca <= t; ca++)
40     {
41         memset(suma, 0, sizeof(suma));
42         memset(sumb, 0, sizeof(sumb));
43         scanf("%d %d", &n, &m);
44         for(int i = 1; i <= n; i++)
45         {
46             for(int j  = 1; j <= m; j++)
47             {
48                 scanf("%d", &a[i][j]);
49                 suma[i][j].c = suma[i][j-1].c + a[i][j];
50             }
51         }
52         for(int i = 1; i <= n; i++)
53         {
54             for(int j  = 1; j <= m; j++)
55             {
56                 scanf("%d", &b[i][j]);
57                 sumb[i][j].c = sumb[i-1][j].c + b[i][j];
58             }
59         }
60         memset(dp, -1, sizeof(dp));
61         int res = dfs(n, m);
62         printf("Case %d: %d\n", ca, res);
63     }
64     return 0;
65 }

 

lightoj1036_记忆化搜索