hdu 3433 A Task Process

本文从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 - ka[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;
}