首页 > 代码库 > HDU 3433 (DP + 二分) A Task Process
HDU 3433 (DP + 二分) A Task Process
题意:
有n个员工,每个员工完成一件A任务和一件B任务的时间给出,问要完成x件A任务y件B任务所需的最短时间是多少
思路:
DP + 二分我也是第一次见到,这个我只能说太难想了,根本想不到。
dp[i][j]表示在t时间内前i个人完成j件A任务后所能完成B任务的最大数量。
代码中还有一些注释。
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 int dp[55][205], a[205], b[205]; 8 int _, n, x, y, kase = 0; 9 10 bool check(int t)11 {12 memset(dp, -1, sizeof(dp));13 dp[0][0] = 0;14 15 for(int i = 1; i <= n; ++i)16 {17 if(dp[i][x] >= y) return true; 18 for(int j = 0; j <= x; ++j)19 {20 if(dp[i - 1][j] != -1)21 {22 int temp = min(t/a[i], x-j); //枚举第i个人可以做的A任务的个数23 for(int k = 0; k <= temp; ++k)24 {25 int t1 = (t - a[i] * k) / b[i]; //计算第i个人做k件A任务,所能做的B任务的个数26 dp[i][j + k] = max(dp[i][j + k], dp[i - 1][j] + t1); //选最优解27 }28 }29 }30 }31 32 if(dp[n][x] >= y) return true;33 return false;34 }35 36 int main(void)37 {38 #ifdef LOCAL39 freopen("3433in.txt", "r", stdin);40 #endif41 42 scanf("%d", &_);43 while(_--)44 {45 scanf("%d%d%d", &n, &x, &y);46 for(int i = 1; i <= n; ++i)47 scanf("%d%d", &a[i], &b[i]);48 49 int l = 0, r = a[1] * x + b[1] * y;50 int ans = r;51 while(l <= r)52 {53 int mid = (l + r) >> 1;54 if(check(mid))55 {56 ans = mid;57 r = mid - 1;58 }59 else l = mid + 1;60 }61 62 printf("Case %d: %d\n", ++kase, ans);63 }64 65 return 0;66 }
HDU 3433 (DP + 二分) A Task Process
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。