Algoogle

Algorithm for Programming Contest

PKU 1946 Cow Cycling

Category: PKU Tag: dp

Cow Cycling

問題概要


N頭の牛がサイクリングしている.
各牛は体力がEある.
先頭の牛は1分間にx進むときx^2の体力を消費し,
後続の牛は1分間にx進むときxの体力を消費する.
体力がなくなった牛はリタイアする.
そのとき1頭以上がD進むのにかかる最小の時間をもとめよ.

解法


DP
dp[i][j][k] := i頭目の体力がj使われていて, k進んでいるときの時間の最小
DP表を更新するときに, 次の牛は今進んでいる距離とちょうど同じ体力しか消費していないことに注意する. つまり次の牛に交代するときの更新の体力の部分はjではなくkに依る(ここではまっていた).

コード


(1946.cpp) download
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
#include <algorithm>
#include <cstdio>
#include <iostream>

using namespace std;

const int inf = int(1e9);
int N, E, D;
int dp[32][128][128];

int main(){
    scanf("%d%d%d", &N, &E, &D);

    for(int i = 0; i < N; i++)
        for(int j = 0; j <= E; j++)
            for(int k = 0; k <= D; k++)
                dp[i][j][k] = inf;
    dp[0][0][0] = 0;
    int ans = inf;
    for(int i = 0; i < N; i++)
        for(int j = 0; j <=f E; j++){
            for(int k = 0; k < D; k++)
                for(int x = 1; k+x <= D; x++){
                    if(i < N-1 and k+x*x <= E) dp[i+1][k+x*x][k+x] = min(dp[i+1][k+x*x][k+x], dp[i][j][k]+1);
                    if(j+x*x <= E) dp[i][j+x*x][k+x] = min(dp[i][j+x*x][k+x], dp[i][j][k]+1);
                }
            ans = min(ans, dp[i][j][D]);
        }
    if(ans == inf) ans = 0;
    printf("%d\n", ans);
    return 0;
}

Comments