Algoogle

Algorithm for Programming Contest

PKU 2228 Naptime

Category: PKU Tag: dp

Naptime

問題概要


1日をN個に分けて, 各時間には寝ている時に得られるutilityが決まっている.
一日Bだけ寝られるとき, 得られるutilityの総和の最大はいくらか.
ただし, 寝始めの時間はutilityが得られなく, 連続して寝る必要はない.

解法


DP
dp[i][j][k] := 時間iにj時間寝て現在の状態がk
状態は, 起きている, 寝始め, 寝ている, の3つ.
ただし, 1日が寝ている状態から始めるのか起きている状態から始めるのかで場合分けする必要がある.
寝ている状態から始めるときは, 一日の終りの時間は寝始め, もしくは寝ている状態でなければならない.
始めの状態は初期化で, 終わりの状態は答えを比較するときに起きている状態を見るかどうかで分ければいい.

コード


(2228.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
33
34
35
36
37
38
39
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

int N, B;
int util[4096];
int dp[2][4096][4];

void calc(){
    for(int i = 0; i < N; i++){
        int s = i%2, t = (i+1)%2;
        memset(dp[t], -1, sizeof(dp[t]));
        for(int j = 0; j <= B; j++){
            for(int k = 0; k < 3; k++){
                dp[t][j][0] = max(dp[t][j][0], dp[s][j][k]);
                if(j < B and dp[s][j][k] >= 0)
                    dp[t][j+1][1+(k>0)] = max(dp[t][j+1][1+(k>0)], dp[s][j][k] + (k>0)*util[i]);
            }
        }
    }
}

int main(){
    scanf("%d%d", &N, &B);
    for(int i = 0; i < N; i++)
        scanf("%d", util+i);
    int ans = 0;
    for(int i = 0; i < 2; i++){
        memset(dp, -1, sizeof(dp));
        dp[0][0][i*2] = 0;
        calc();
        for(int k = i; k < 3; k++)
            ans = max(ans, dp[N%2][B][k]);
    }
    printf("%d\n", ans);
    return 0;
}

Comments