USACO备考冲刺必刷题 | P2722 Score Inflation

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

【题目描述】

我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。

你的任务是写一个程序来告诉 USACO 的职员,应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。

【输入】

输入的第一行是用空格隔开的两个整数，分别代表竞赛时间?m?和题目类?n。

第 2 到第 (n+1) 行，每行两个用空格隔开的整数，第 (i+1) 行的整数?pi,ti?分别代表解决第?i?类题得到的分数和需要花费的时间。

既然是某一类题目，那么这一类题目可以重复选择。

【输出】

输出一行一个整数，代表最大的总分。

【输入样例】

300 4
100 60
250 120
120 100
35 20

【输出样例】

605

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int m, n;
int w[10005], c[10005];
int dp[10005];
int main()
{
    cin >> m >> n;  // 输入m和n
    for (int i=1; i<=n; i++) {  // 依次输入n个种类的分数和花费时间
        cin >> c[i] >> w[i];
    }
    for (int i=1; i<=n; i++) {  // 按照完全背包模板填写（滚动数组版本）
        for (int j=w[i]; j<=m; j++) {
            dp[j] = max(dp[j], dp[j-w[i]]+c[i]);
        }
    }
    cout << dp[m] << endl;  // 
    return 0;
}

【运行结果】

300 4
100 60
250 120
120 100
35 20
605