Algoogle

Algorithm for Programming Contest

PKU 3624 Charm Bracelet

Category: PKU Tag: dp

Charm Bracelet

問題概要


解法


そのままナップザック問題
dp[j] := 重さj以下の時の価値の最大

コード


(3624.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <cstdio>

using namespace std;

int N, M;
int dp[13000];
int p[3410], w[3410];

int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < N; i++)
        scanf("%d%d", w+i, p+i);
    for(int i = 0; i < N; i++)
        for(int j = M - w[i]; j >= 0; j--)
            dp[j+w[i]] = max(dp[j+w[i]], dp[j]+p[i]);
    int ans = 0;
    for(int i = 0; i <= M; i++)
        ans = max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}

Comments