这题是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; }