hdu 3433 A Task Process(dp+二分)

题意：n个人，要完成a个x任务， b个y任务。

求，最短的时间

思路：由于时间较大，用二分来找时间。

dp[i][j]表示 i个人完成j个x任务，最多能完成的y任务个数

这个题不是很好想，还参考了一下大神的博客

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 1000+10;
 8 int d[55][205];
 9 
10 int _max(int a, int b)
11 {
12     return a>b?a:b;
13 }
14 int _min(int a, int b)
15 {
16     return a>b?b:a;
17 }
18 int main()
19 {
20     int t, i, j, k, n, x, y, ca;
21     int a[maxn], b[maxn];
22     int low, high, mid, cnt, t1;
23     scanf("%d", &t);
24     for(ca = 1; ca <= t; ca++)
25     {
26         low = 0;
27         high = 0;
28         scanf("%d%d%d", &n, &x, &y);
29         for(i = 1; i <= n; i++)
30         {
31             scanf("%d%d", &a[i], &b[i]);
32             high += x*a[i] + y*b[i];
33         }
34         while(high>low)
35         {
36             mid = (low+high)/2;
37             memset(d, -1, sizeof(d));
38             d[0][0] = 0;
39             for(i = 1; i <= n; i++)
40                 for(j = 0; j <= x; j++)
41                 {
42                     if(d[i-1][j]!=-1)
43                     {
44                         cnt = _min(mid/a[i], x-j);
45                         for(k = 0; k <= cnt; k++)
46                         {
47                             t1 = (mid-k*a[i])/b[i];
48                             if(d[i][j+k]<d[i-1][j]+t1)
49                             d[i][j+k] = d[i-1][j]+t1;
50                         }
51                     }
52                 }
53             if(d[n][x]>=y)
54                 high = mid;
55             else
56                 low = mid+1;
57         }
58         printf("Case %d: %d
", ca, high);
59     }
60     return 0;
61 }