Algoogle

Algorithm for Programming Contest

PKU 3661 Running

Category: PKU Tag: dp

Running

問題概要


N分間のうち, 走る時間と休む時間を決めた時, N分目が終了した時に疲労が0の最大の走行距離をもとめる.
時間iに走った場合Di進んで, 疲労がj溜まってる時休む場合, j分間休まなければならない.
また疲労はMを超えてはならない.

解法


dp[i][j] := i分目が終了した時に疲労がjのときの最大の走行距離

コード


(3661.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
#include <algorithm>
#include <cstdio>

using namespace std;

int N, M;
int D[10010];
int dp[10010][512];

int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < N; i++)
        scanf("%d", D+i);

    dp[0][0] = 0;
    for(int i = 0; i < N; i++){
        dp[i+1][0] = max(dp[i+1][0], dp[i][0]);
        for(int j = 0; j <= min(i, M); j++){
            if(j < M) dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + D[i]);
            if(i+j <= N)dp[i+j][0] = max(dp[i+j][0], dp[i][j]);
        }
    }

    printf("%d\n", dp[N][0]);
    return 0;
}

Comments