CCF-CSP第41次认证第二题——机器人项目管理
题目描述
小 P 计划招募 n 个机器人完成一个项目：每个机器人负责其中的一项任务，编号从 1 到 n，任务之间互不干扰。如果完成任务 i 的耗时为 tit，则该项目总耗时为 t1+t2+⋯+tn。
作为项目管理者，小 P 可以用有限的预算为机器人们购买咖啡加油。其中负责任务 ii 的机器人，最多可以喝 ai 杯咖啡，从而将该任务耗时缩短 bibi（最终耗时即为 ti−bi）。
根据任务的特性和机器人的偏好，n 项任务可分为“灵活型”和“普通型”两类，详情参见附件资料（重要）。
已知小 P 可以为机器人们提供最多 mm 杯咖啡，试计算完成整个项目的最短时间。
输入格式
从标准输入读入数据。
输入的第一行包含空格分隔的两个正整数 n 和 m，分别表示任务数量和咖啡数量。
接下来 n 行，每行包含空格分隔的四个整数 oi、ti、ai 和 bi，表示一个任务。其中 oi∈{0,1} 表示任务类别，oi=0 表示灵活型、oi=1 表示普通型；其余变量含义如上所述，输入数据保证 ti>bi，即缩短后的耗时仍大于零。
输出格式
输出到标准输出。
输出一个实数，表示完成整个项目的最短时间。
样例1输入
3 5 0 2 3 1 0 3 4 2 0 4 5 2 样例1输出
6.6 样例1解释
三个任务均为灵活型，初始总耗时为 2+3+4=9。最优方案为：给任务二分配 4 杯咖啡，耗时缩短 2；给任务三分配 11 杯咖啡，耗时相应缩短 25=0.4。综上，完成整个项目最短时间为 9−2−0.4=6.6。
样例2输入
5 62 0 10 2 1 0 10 1 1 1 500 40 360 1 600 50 500 1 400 20 150 样例2输出
1008.5 样例2解释
初始总耗时为 1520。最优方案为：给任务三分配 40 杯咖啡，耗时缩短 360；给任务五分配 20 杯咖啡，耗时缩短 150；给任务一和二各分配 1 杯咖啡，耗时分别缩短 0.5 和 1。综上，完成整个项目最短时间为 1520−360−150−0.5−1=1008.5。
子任务
80% 的测试点满足：所有任务均为灵活型任务，且对于每个任务 i 有 0<ai≤20；
全部的测试点满足：0<n≤200、0<m≤1000，且对于每个任务 ii 有 0<ai≤100、0<bi<ti≤104。
评分方式
输出结果与标准答案相比绝对误差小于 0.001 即可，推荐保留六位小数输出结果。
题解
基础的背包问题，单纯的01背包，需要把灵活型的咖啡拆成一杯一杯的再存入候选项中，最后用01背包做就行，这道题好像没有卡复杂度，直接拆就行，不用二进制优化。
0-1背包模版
int main() { cin>>n>>m; for(int i=1;i<=n;i++){ cin>>v[i]>>w[i]; } for(int i=1;i<=n;i++) for(int j=m;j>=v[i];j--) f[j]=max(f[j],f[j-v[i]]+w[i]); cout<<f[m]; return 0; }代码如下
#include<bits/stdc++.h> using namespace std; const int N=210,M=1010; int n,m,o,t,a[N],sum,cnt; double b[N],dp[M]; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>o>>t>>a[cnt]>>b[cnt]; sum+=t; if(o==0){ int temp=cnt; for(int j=1;j<a[temp];j++){ a[++cnt]=1; b[cnt]=b[temp]/(double)a[temp]; } b[temp]=b[temp]/(double)a[temp]; a[temp]=1; } cnt++; } for(int i=0;i<cnt;i++) for(int j=m;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]); cout<<sum-dp[m]<<endl; }
