POJ 1946 - Cow Cycling

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

概要

N 頭の牛が一列に並んで D 周のレースをする．

すべての牛は最初 E のエネルギーを持っている． 単位時間に x 周の速度で走ると，単位時間に先頭の牛は x*x のエネルギーを消費し，そうでない牛は x のエネルギーを消費する． エネルギーの無くなった牛は走ることができない．

牛はどのタイミングでもドロップアウトすることができるし，どのタイミングでも先頭の牛を交代できる． このときにかかる時間は無視してよい．

ゴール時間が最速になるように走ったとき，そのゴール時間を出力する．

制約

• 1 <= N <= 20
• 100 <= D <= 100
• 100 <= E <= 100

解法

dp[n][e][d] := d 週目を n 頭目の牛を先頭として走っており，先頭の牛のこれまでに消費したエネルギーが e のときの最短時間

として DP．

単位時間毎に見ると

• 先頭の牛をそのままにして x の速度で走る
• 先頭の牛をドロップアウトさせて次の牛が x の速度で走る

の2パターンしか無いので，この2つで DP 表を更新していく．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N, E, D;
 8   cin >> N >> E >> D;
 9   static const int INF = 10000;
10   static int dp[20][101][101];
11   for (int i = 0; i < N; i++) {
12     for (int j = 0; j <= E; j++) {
13       fill_n(dp[i][j], D+1, INF);
14     }
15   }
16   dp[0][0][0] = 0;
17   for (int n = 0; n < N; n++) {
18     for (int e = 0; e <= E; e++) {
19       for (int d = 0; d <= D; d++) {
20         for (int x = 1; x <= 10; x++) {
21           const int dd = min(d+x, D);
22           if (e+x*x <= E) {
23             dp[n][e+x*x][dd] = min(dp[n][e+x*x][dd], dp[n][e][d]+1);
24           }
25           if (n < N-1 && d+x*x <= E) {
26             dp[n+1][d+x*x][dd] = min(dp[n+1][d+x*x][dd], dp[n][e][d]+1);
27           }
28         }
29       }
30     }
31   }
32   int ans = INF;
33   for (int i = 0; i < N; i++) {
34     for (int j = 0; j <= E; j++) {
35       ans = min(ans, dp[i][j][D]);
36     }
37   }
38   cout << ans << endl;
39   return 0;
40 }