POJ 1042 - Gone Fishing

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

概要

n 個の湖を順番に進みながら釣りをする． i 番目の湖では，最初の5分間で f[i] 匹釣れ，以降5分間に釣れる数が d[i] ずつ減っていく． i 番目の湖から次の i+1 番目の湖へ行くのに 5 * t[i] 分かかる．

1 番目の湖からスタートして，h 時間で最大何匹釣れるかを答え，そのとき各湖で何分間いたかを答える． (n 番目の湖まで進む必要はない)

複数の答えがある場合，なるべく最初のほうの湖に長く滞在するようにした場合を答える．

制約

解法

DP． 経路を答えるのが面倒．

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF && N != 0) {
 9     int H;
10     scanf("%d", &H);
11     const int M = 12*H;
12     vector<int> f(N);
13     for (int i = 0; i < N; i++) {
14       scanf("%d", &f[i]);
15     }
16     vector<int> d(N);
17     for (int i = 0; i < N; i++) {
18       scanf("%d", &d[i]);
19     }
20     vector<int> t(N-1);
21     for (int i = 0; i < N-1; i++) {
22       scanf("%d", &t[i]);
23     }
24     vector<int> tt(N-1);
25     tt[0] = t[0];
26     for (int i = 1; i < N-1; i++) {
27       tt[i] = tt[i-1] + t[i];
28     }
29 
30     vector<vector<int> > dp(N, vector<int>(M+1, 0));
31     vector<vector<int> > prev(N, vector<int>(M+1, -1));
32     for (int i = 0, x = 0, r = f[0]; i <= M; i++, x += r, r = max(r - d[0], 0)) {
33       dp[0][i] = x;
34     }
35     for (int i = 1; i < N; i++) {
36       for (int j = tt[i-1]; j <= M; j++) {
37         for (int k = j, x = 0, r = f[i]; k <= M; k++, x += r, r = max(r - d[i], 0)) {
38           const int y = dp[i-1][j-t[i-1]] + x;
39           if (y >= dp[i][k]) {
40             dp[i][k] = y;
41             prev[i][k] = j - t[i-1];
42           }
43         }
44       }
45     }
46 
47     int ans = 0, idx = 0;
48     for (int i = 0; i < N; i++) {
49       if (ans < dp[i][M]) {
50         ans = dp[i][M];
51         idx = i;
52       }
53     }
54     int m = M;
55     vector<int> intervals(N, 0);
56     for (int i = idx; i > 0; i--) {
57       intervals[i] = 5*(m - prev[i][m] - t[i-1]);
58       m = prev[i][m];
59     }
60     printf("%d", 5*m);
61     for (int i = 1; i < N; i++) {
62       printf(", %d", intervals[i]);
63     }
64     printf("\nNumber of fish expected: %d\n\n", ans);
65   }
66   return 0;
67 }
poj/1042.cc