首页 > 代码库 > Lightoj 1036(dp)

Lightoj 1036(dp)

2024-07-03 14:42:33   227人阅读

题意：在一个矿场上有两种矿石，分别对应两个处理他的工厂分别在左边与上边。要求你铺设运输设备每个方格可以向左、上或不运。矿石在运输途中不能转弯，问你最多能运多少矿石到相应的工厂加工。

思路：我们可以注意到由于不能转弯的原因，所以一旦左边的格子被铺上向左的他也也铺上向左的比较有利，否则左边的就白铺了（铺了也运不到）这样每种格子两种选择，就可以写dp方程了：

dp[i][j][0]:当前格子不铺的最大收获

dp[i][j][1]:当前格子向上的最大收获

dp[i][j][2]:当前格子向左的最大收获

F(a, b) : a = max(a, b)

G(i, j): max(dp[i][j][0], dp[i][j][1], dp[i][j][2])

dp[i][j][0]:F(dp[i][j][0], max(G(i-1,j)+mpa[i][j-1], G(i, j-1)+mpb[i-1][j]))

dp[i][j][1]:F(dp[i][j][1], max(G(i, j-1)+mpb[i][j]), dp[i-1][j][1]+mpa[i][j-1]+mpb[i][j]-mpb[i-1][j]))

dp[i][j][2]:F(dp[i][j][2], max(G(i-1, j)+mpa[i][j], dp[i][j-1][2]+mpb[i-1][j]+mpa[i][j]-mpa[i][j-1]))

代码如下：

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-05-08 13:35
 5  * Filename     : L_1035.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int LEN = 1010;
34 int dp[LEN][LEN][3], n, m, mpa[LEN][LEN], mpb[LEN][LEN];
35 
36 void F(int &a, int b){
37     a = max(a, b);
38 }
39 
40 int G(int a, int b){
41     int ret = max(dp[a][b][1], dp[a][b][2]);
42     ret = max(ret, dp[a][b][0]);
43     return ret;
44 }
45 
46 int main()
47 {
48 //    freopen("in.txt", "r", stdin);
49 
50     int T, kase = 1, tmp;
51     scanf("%d", &T);
52     while(T--){
53         scanf("%d%d", &n, &m);
54         memset(dp, 0, sizeof dp);
55         memset(mpa, 0, sizeof mpa);
56         memset(mpb, 0, sizeof mpb);
57         for(int i=1; i<=n; i++){
58             for(int j=1; j<=m; j++){
59                 scanf("%d", &tmp);
60                 mpa[i][j] = mpa[i][j-1] + tmp;
61             }
62         }
63         for(int i=1; i<=n; i++){
64             for(int j=1; j<=m; j++){
65                 scanf("%d", &tmp);
66                 mpb[i][j] = mpb[i-1][j] + tmp;
67             }
68         }
69         for(int i=1; i<=n; i++){
70             for(int j=1; j<=m; j++){
71                 F(dp[i][j][0], max(G(i-1,j)+mpa[i][j-1], G(i, j-1)+mpb[i-1][j]));
72                 F(dp[i][j][1], G(i, j-1)+mpb[i][j]);
73                 F(dp[i][j][2], G(i-1, j)+mpa[i][j]);
74                 F(dp[i][j][1], dp[i-1][j][1]+mpa[i][j-1]+mpb[i][j]-mpb[i-1][j]);
75                 F(dp[i][j][2], dp[i][j-1][2]+mpb[i-1][j]+mpa[i][j]-mpa[i][j-1]);
76             }
77         }
78         printf("Case %d: %d\n", kase ++, G(n, m));
79     }
80     return 0;
81 }
View Code

 


联系
我们