P2722 总分 Score Inflation

Link

Solution

完全背包

Code

#include <algorithm>
#include <iostream>
const int maxn = 45000*500 + 10;
using namespace std;

int m, n;

int score[maxn], cost[maxn], f[maxn];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++)cin >> score[i] >> cost[i];
    for (int i = 1; i <= n; i++)
        for (int j = cost[i]; j <= m; j++)
            f[j] = max(f[j], f[j - cost[i]] + score[i]);
    cout << f[m] << endl;
    return 0;
}