星星博客 »  > 

【ACWing】1377. 得分通胀

题目地址:

https://www.acwing.com/problem/content/1379/

学生们在USACO的竞赛中得分越多,我们就越感到高兴。所以我们要尽量将竞赛设计的能够让更多人得到更高的分。为了达到这一目的,请你帮助我们选择一些题目作为比赛用题。共有 N N N种类别的题可以让我们进行选择,同一类别的题做对所花的时间以及得到的分数都是相同的。每种类型的题目出现在一次竞赛中的数量不限,竞赛的时长为 M M M,即所选题目的总耗时不得超过 M M M,但可以小于 M M M。请问,我们如何安排各种类型的题目在竞赛中出现的数量,能够使得用户的得分最多。竞赛中不一定要出现所有类型的题目。输出用户可能的最高得分。

输入格式:
第一行包含两个整数 M , N M,N M,N,分别表示竞赛时长以及题目种类数量。接下来 N N N行,每行包含两个整数 p , t p,t p,t,分别表示一种类型题目的分数以及耗时。

输出格式:
输出一个整数,表示用户可能得到的最大分数。

数据范围:
1 ≤ M , N , p , t ≤ 1 0 4 1≤M,N,p,t≤10^4 1M,N,p,t104

其实可以看成是个完全背包问题,可以用动态规划来做。代码如下:

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010;
int n, m;
int w[N], v[N];
int f[N];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
    	// 完全背包里体积从小到大更新
        for (int j = w[i]; j <= m; j++)
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    cout << f[m] << endl;

    return 0;
}

时间复杂度 O ( N M ) O(NM) O(NM),空间 O ( M ) O(M) O(M)

相关文章