这题是01背包的板子题,唯一的难点就是获得的价值会随着时间的变化而变化,所以要确定一个做题的顺序,要使得到的分数最多,也就是要使随着时间浪费的分数最小化
先看一个简单的:如果只有两道题 起始分数分别为 随时间的变化分别为 所花费的时间分别为
若先取 则有获得的总分数为 也就是说由于时间关系浪费的分数为
同理可得,若先取 由于时间浪费的分数为
只要比较两式即可得到排序的方法,直接观察两式子貌似没什么规律(本蒟蒻看不出规律),所以我们考虑对式子变形
两式子除以 即可发现
第一个式子变成了
第二个式子变形后为
去掉相同的部分发现 浪费的时间只和 有关,
再稍微缕一下逻辑关系 越大 浪费的时间越多,所以排序越靠后,即越大 越前
好了,排序问题解决了,剩下的就是套01背包的板子

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define endl '\n'
#define int long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int N = 5e6 + 7;
const int M = 5e5 + 7;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

struct node {
    int v, rt, w;//v,rt,w含义与上文解释相同
}s[M];

ll dp[M];

bool cmp(node x, node y) { return x.w * y.rt < y.w * x.rt; } //重载排序

ll colve(int n, int W) {//01背包板子改版
    for(int i = 1; i <= n; ++i) 
        for(int j = W; j >= s[i].w; -- j) 
            dp[j] = max(dp[j], dp[j - s[i].w] + s[i].v - j * s[i].rt);
    ll ans = 0; 
    for(int i = W; i >= 1; -- i) ans = max(ans, dp[i]); //注意有出现得到的分数为负数的情况
    return ans;        
}

signed main() { ios;
    int n, W; cin >> n >> W;
    for(int i = 1; i <= n; ++i) cin >> s[i].v;
    for(int i = 1; i <= n; ++i) cin >> s[i].rt;
    for(int i = 1; i <= n; ++i) cin >> s[i].w;
    sort(s + 1, s + n + 1, cmp);  
    cout << colve(n, W) << endl; 
    return 0;
}