Algoogle

Algorithm for Programming Contest

PKU 3257 Cow Roller Coaster

Category: PKU Tag: dp

Cow Roller Coaster

問題概要


N個の要素があり, それらは始点と幅, 楽しさとコストを持っている.
コストの和がB以下で長さLをちょうどカバーするような組み合わせのうち, 楽しさの和が最大のものを求める.

解法


dp[i][j] := 地点 i でコストの和が j のときの楽しさの最大
各地点から始まる要素について幅とコストを足したdpの場所を更新していく
dp表は結構スカスカなので更新されてない場所を飛ばせば計算間に合う.

コード


(3257.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
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

struct S{ int w, f, c;};

int L, N, B;
vector<S> cmp[1024];
int dp[1024][1024];

int main(){
    scanf("%d%d%d", &L, &N, &B);
    for(int i = 0; i < N; i++){
        int x, w, f, c; scanf("%d%d%d%d", &x, &w, &f, &c);
        cmp[x].push_back((S){w,f,c});
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 0; i < L; i++)
        for(int j = 0; j < B; j++)
            if(dp[i][j] >= 0)
                for(int k = 0; k < cmp[i].size(); k++){
                    int ni = i + cmp[i][k].w, nj = j + cmp[i][k].c;
                    if(nj <= B) dp[ni][nj] = max(dp[ni][nj], dp[i][j]+cmp[i][k].f);
                }
    int ans = -1;
    for(int i = 0; i <= B; i++)
        ans = max(ans, dp[L][i]);
    printf("%d\n", ans);
    return 0;
}

Comments