为了庆贺班级在校运动会上取得全校第一名成绩,班主任决定开一场庆功会,为此拨款购买奖品犒劳运动员。

输入格式

第一行包含两个数字 nm,其中:

  • n 代表希望购买的奖品的种数
  • m 表示拨款金额

接下来的 n 行,每行包含三个数字 vws,分别表示第 i 种奖品的价格、价值和能购买的最大数量(买 0 件到 s 件均可)。

输出格式

一行:一个数字,表示此次购买能获得的最大的价值(注意!不是价格)。

数据范围

  • n ≤ 500
  • m ≤ 6000
  • v ≤ 100
  • w ≤ 1000
  • s ≤ 10

输入样例

5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1

输出样例

1040

代码实现

#include <iostream>
using namespace std;
const int N = 6e4 + 10;

int n, V, v, w, s, dp[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> V;
    while(n--) {
        cin >> v >> w >> s;
        int t = 1;
        while(t <= s) {
            for (int i = V; i >= t * v; --i) dp[i] = max(dp[i], dp[i - t * v] + t * w);
            s -= t;
            t <<= 1;
        }
        if (s) for (int i = V; i >= s * v; --i) dp[i] = max(dp[i], dp[i - s * v] + s * w);
    }
    cout << dp[V];
    return 0;
} 
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status