2 条题解
-
8
#include<bits/stdc++.h> using namespace std; int m,n,f[1000005]; struct T { int a; int b; int c; double p; }t[100005]; bool cmp(T x, T y) { return x.p > y.p; } int main() { cin>>m>>n; for(int i=1;i<=n;i++) { cin>>t[i].a; } for(int i=1;i<=n;i++) { cin>>t[i].b; } for(int i=1;i<=n;i++) { cin>>t[i].c; } for (int i = 1; i <= n; i++) { t[i].p = 1.0 * t[i].b / t[i].c; } sort(t + 1, t + n + 1, cmp); int ans = 0; f[0]=0; for(int i = 1; i <= n; i++) { for(int j = m; j >= t[i].c; j--) { f[j] = max(f[j], f[j - t[i].c] + t[i].a - t[i].b * j); ans = max(ans, f[j]); } } cout<<ans; return 0; }
-
4
本题是需要用到之前学习过的邻项交换排序进行最优子结构和无后效性分析,假设有两道题的初始分数,减少分数和耗时分别为a1,b1,c1和 a2,b2,c2。假设目前时间为t; 先做题1再做题2得到的分数:(1式) a1 - b1 * (c1 + t) + a2 - b2 * (c1 + c2 + t)
先做题2再做题1得到的分数:(2式) a2 - b2 * (c2 + t) + a1 - b1 * (c1 + c2 + t)
若先做题1再做题2得到的分数更多, 则需要满足(1式)>(2式)
化简得到:b1 * c2 > b2 * c1 即排序规则为: b1 / c1 > b2 / c2 (需要注意数据类型应转换为double型)
参考代码
bool cmp(T x, T y) { return x.p > y.p; }
for (int i = 1; i <= n; i++) { t[i].p = 1.0 * t[i].b / t[i].c; } sort(t + 1, t + n + 1, cmp); int ans = 0; for(int i = 1; i <= n; i++) { for(int j = m; j >= t[i].c; j--) { f[j] = max(f[j], f[j - t[i].c] + t[i].a - t[i].b * j); ans = max(ans, f[j]); } }
- 1
信息
- ID
- 384
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 2
- 标签
- (无)
- 递交数
- 313
- 已通过
- 186
- 上传者