POJ 2948 - Martian Mining

http://poj.org/problem?id=2948

概要

n * m のグリッド上の各マスに，上に運ぶべき鉱物と左に運ぶべき鉱物がいくつかある． 各マスに上方向か左方向のベルトコンベアを設置して，鉱物を運ぶ． ただし，ベルトコンベアによる運搬路は途中で曲がってはならない．

ベルトコンベアをうまく設置して，上に運ぶべき鉱物を上に運べた数と左に運ぶべき鉱物を左に運べた数の和を最大化する問題．

制約

解法

途中で曲がれないので，最適な配置は ←↑↑↑↑ ←←←↑↑ ←←←↑↑ ←←←↑↑ ←←←←← のように，各行のどこかの列を境に左と上に分かれ，しかもその境界は単調非減少．

したがって dp[i][j] = i 行目で j 列目を境界にしたときの最大値 を dp[i][j] = max { dp[i-1][k] + ((i,0) から (i,j) までの左に運ぶべき鉱物の合計) + ((0,j) から (i,j) までの上に運ぶべき鉱物の合計) } for k = 1 .. j と更新していく DP で解ける．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N, M;
 8   while (scanf("%d %d", &N, &M) != EOF && N != 0) {
 9     static int left[500][501];
10     for (int i = 0; i < N; i++) {
11       left[i][0] = 0;
12       for (int j = 1; j <= M; j++) {
13         scanf("%d", &left[i][j]);
14         left[i][j] += left[i][j-1];
15       }
16     }
17     static int up[500][501];
18     for (int i = 0; i < N; i++) {
19       up[i][0] = 0;
20       for (int j = 0; j < M; j++) {
21         scanf("%d", &up[i][j]);
22       }
23       up[i][M] = 0;
24       for (int j = M-1; j >= 0; j--) {
25         up[i][j] += up[i][j+1];
26       }
27     }
28 
29     static int dp[500][501];
30     for (int i = 0; i < N; i++) {
31       fill_n(dp[i], M+1, 0);
32     }
33     for (int j = 0; j <= M; j++) {
34       dp[0][j] = left[0][j] + up[0][j];
35     }
36     for (int i = 1; i < N; i++) {
37       for (int j = 0; j <= M; j++) {
38         dp[i][j] = 0;
39         for (int k = 0; k <= j; k++) {
40           dp[i][j] = max(dp[i][j], dp[i-1][k] + left[i][j] + up[i][j]);
41         }
42       }
43     }
44     printf("%d\n", *max_element(dp[N-1], dp[N-1]+M+1));
45   }
46   return 0;
47 }
poj/2948.cc