P2430 严酷的训练

Link

Solution

01背包

Code

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

int x, y, m, n, t;

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

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