POJ 3661 - Running

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

概要

ランニングをする。各 \(i\) 分目に、

• 走って距離 \(D_i\) だけ進み、exhaustion factor を1増やす
• 休憩して exhaustion factor を1減らす (ただし、既に 0 だった場合は 0 のまま)

のいずれかの行動を選べる。

exhaustion factor とは、最初は 0 であり、どのタイミングでも \(M\) を越えてはならない。 また、一度休憩を始めたら exhaustion factor が 0 になるまでずっと休憩し続けなければならない。 さらに、ゴールするときは exhaustion factor は 0 でなければならない。

\(N\) 分間走ったとき、最大でどれくらいの距離を走ることができるかを答える。

制約

• \(1 \le N \le 10 ^ 4\)
• \(1 \le D_i \le 10 ^ 3\)
• \(1 \le M \le 500\)

解法

DP。 i 分後に exhaustion factor が j であったときの最大の距離を dp[i][j] とすると、

• 休憩を選ぶと、次に動けるのは i+j 分目なので、 dp[i+j] = max(dp[i+j], dp[i][j])
• 走ることを選ぶと dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + D[i])

と更新できる。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N, M;
 8   scanf("%d %d", &N, &M);
 9   static int D[10000];
10   for (int i = 0; i < N; i++) {
11     scanf("%d", &D[i]);
12   }
13 
14   static int dp[10001][501];
15   static int INF = 10000000;
16   for (int i = 0; i <= N; i++) {
17     fill_n(dp[i], M+1, -INF);
18   }
19   dp[0][0] = 0;
20   for (int i = 0; i < N; i++) {
21     for (int j = 0; j <= M; j++) {
22       // choose rest
23       const int k = j == 0 ? i+1 : i+j;
24       if (k <= N) {
25         dp[k][0] = max(dp[k][0], dp[i][j]);
26       }
27 
28       // choose run
29       if (j < M) {
30         dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + D[i]);
31       }
32     }
33   }
34   printf("%d\n", dp[N][0]);
35   return 0;
36 }