本文从WordPress迁移而来, 查看全部WordPress迁移文章
二分答案 + 背包
题意：给出n个工人，它们做A项目花费a[i]时间，做B项目花费b[i]时间。现在给出x个A项目和y个B项目，要做完它们最短时间是多少。不同工人可以同时工作，一个工人不能同时做两个工作
这题注意一个显而易见又易被忽略的条件，工人们是可以同时工作的，所以任何一个工人它的工作不受别人影响也不影响别人，所以不要老想着选什么最小值最快的，它们都是可以一起工作的，一起工作，一定比一个人工作要快。
这题要用到二分答案，我们最后要求的是完成X个A项目和,Y个B项目的最小时间，所以我们就二分时间。时间的上限可以选一个很大的数，不影响结果，但是不需要，上限可以设为 high = a[1] * x + b[1] * y，这个意思就是全部工作交给第1个人全部做完去，为什么这个可以做上限，是因为一个人做完了全部工作，肯定比所有人协力去做要慢（high = max{ a[i] * x + b[i] * y} 这种想法固然是对的，但是也没必要，high = a[1] * x + b[1] * y 完全足够了）
枚举了时间，接着就检验，用dp检验。设置一个巧妙的状态,dp[i][A]，在限定时间内前i个人做完A个工作后，能做最多的B工作数。那么目标状态就是dp[n][x]，即在限定时间内n个人做完了全部的x个A工作，最多能做的B工作数
如果dp[n][x] >= y，说明能做够y个B项目，这个时间就是一个合法的时间，是一个可行解，那么就可以试着把这个时间缩小，所以向下二分
如果dp[n][x] < y,说明做不够y个B项目，时间不够，那么只好增大时间，所以向上二分
根据这个dp的意义很容易想到是个背包，那么就可以状态转移了
dp[i][A] = max{ dp[i-1][A-k] + k * (time - k*a[i]) }
(即前i-1个人做了A-k个A项目，第i个人做了k个A项目，第i个人剩下的时候都用来做B项目，加起来就是最大值)
写DP的时候注意一些细节，一些状态去不到的要及时continue或者break掉
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 55
#define M 210
#define INF 0x3f3f3f3f
#define cl memset
int n,x,y;
int a[N],b[N];
int dp[N][M];
void solve(int time){
cl(dp,-1,sizeof(dp));
for(int A = 0; A <= x; A++){
if(A*a[1] > time) break;
dp[1][A] = (time - A * a[1]) / b[1];
}
for(int i = 2; i <= n; i++)
for(int A = 0; A <= x; A++)
for(int k = 0; k <= A; k++){
if(k*a[i] > time) break;
if(dp[i-1][A-k] < 0) continue;
dp[i][A] = max(dp[i][A] , dp[i-1][A-k] + (time-k*a[i])/b[i]);
}
}
int main(){
int cas;
scanf("%d",&cas);
for(int c = 1; c <= cas ; c++){
scanf("%d%d%d",&n,&x,&y);
for(int i = 1; i <= n; i++){
scanf("%d%d",&a[i],&b[i]);
}
int low = 1 , high = a[1]*x+a[1]*y , mid , ans = 1;
while(low <= high){
mid = (low + high) >> 1;
solve(mid);
if(dp[n][x] >= y){
ans = mid;
high = mid - 1;
}
else
low = mid + 1;
}
printf("Case %d: %d\n",c,ans);
}
return 0;
}
|