解題區/解題區 - UVa

UVa 12870 - Fishing

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

有 N x M 個魚池，接著要進行釣魚，為了防止生態滅絕，必須要餵兩次魚才能釣一次魚。餵魚時必須嚴格往右下角餵，釣魚也必須依序嚴格往右下角餵。很特別的是，釣魚、餵魚不影響魚池內的數量 (WTF)。餵魚成本、釣魚獲益都等於該魚池的數量，可以選擇在同一個魚池餵魚或者是釣魚。

求最大獲益為何？

Sample Input

1
2
3
4
5
6
7
8
9
10
2
4 4
1 1 1 4
1 3 1 1
1 1 2 1
1 1 1 1
3 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Sample Output

1
2
2
0

Solution

兩個路徑獨立，分開計算最大獲益路徑，直接著手 dp，找左上到右下，挑數個進行釣魚和餵魚動作。

每一個位置多紀錄已經挑了多少個魚池動作，隨後窮舉到底要怎麼組合來得到最佳獲益。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 128
int dp[MAXN][MAXN][MAXN];
int dp2[MAXN][MAXN][MAXN];
int main() {
    int testcase;
    int n, m, A[128][128];
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                scanf("%d", &A[i][j]);
        int nm = min(n, m);
        int lenMAX[128] = {}, lenMIN[128] = {};
        for (int i = 0; i <= nm; i++) {
            lenMAX[i] = 0;
            lenMIN[i] = -0x3f3f3f3f;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k <= nm; k++) {
                    dp[i][j][k] = 0, dp2[i][j][k] = -0x3f3f3f3f;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j][1] = max(dp[i][j][1], A[i][j]);
                dp2[i][j][1] = max(dp2[i][j][1], -A[i][j]);
                for (int k = 1; k <= nm; k++) {
                    if (i > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
                        dp2[i][j][k] = max(dp2[i][j][k], dp2[i-1][j][k]);
                    }
                    if (j > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
                        dp2[i][j][k] = max(dp2[i][j][k], dp2[i][j-1][k]);
                    }
                    if (i > 0 && j > 0) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-1] + A[i][j]);
                        dp2[i][j][k] = max(dp2[i][j][k], dp2[i-1][j-1][k-1] - A[i][j]);
                    }
//                    printf("%d %d %d %d\n", i, j, k, dp2[i][j][k]);
                }
                for (int k = 1; k <= nm; k++)
                    lenMAX[k] = max(lenMAX[k], dp[i][j][k]), lenMIN[k] = max(lenMIN[k], dp2[i][j][k]);
            }
        }
        int ret = 0;
        for (int i = 2; i <= nm; i += 2) {
            ret = max(ret, lenMAX[i/2] + lenMIN[i]);
//            printf("%d %d %d\n", i, lenMAX[i/2], lenMIN[i]);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
 9999
 4 4
 1 1 1 4
 1 3 1 1
 1 1 2 1
 1 1 1 1
 3 5
 1 1 1 1 1
 1 1 1 1 1
 1 1 1 1 1
 3 4
 0 0 1 0
 0 0 2 0
 0 1 0 0
 2 2
 0 1
 2 0
 2 3
 10 20 30
 30 4 50
 3 2
 10 20
 30 30
 4 50
 */