首页 > ACM题库 > HDU-杭电 > HDU 3433-A Task Process-动态规划-[解题报告]HOJ
2014
03-23

HDU 3433-A Task Process-动态规划-[解题报告]HOJ

A Task Process

问题描述 :

There are two kinds of tasks, namely A and B. There are N workers and the i-th worker would like to finish one task A in ai minutes, one task B in bi minutes. Now you have X task A and Y task B, you want to assign each worker some tasks and finish all the tasks as soon as possible. You should note that the workers are working simultaneously.

输入:

In the first line there is an integer T(T<=50), indicates the number of test cases.

In each case, the first line contains three integers N(1<=N<=50), X,Y(1<=X,Y<=200). Then there are N lines, each line contain two integers ai, bi (1<=ai, bi <=1000).

输出:

In the first line there is an integer T(T<=50), indicates the number of test cases.

In each case, the first line contains three integers N(1<=N<=50), X,Y(1<=X,Y<=200). Then there are N lines, each line contain two integers ai, bi (1<=ai, bi <=1000).

样例输入:

3
2 2 2
1 10
10 1
2 2 2
1 1
10 10

3 3 3
2 7
5 5
7 2

样例输出:

Case 1: 2
Case 2: 4
Case 3: 6

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <cmath>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 205;
int dp[N],a[N],b[N];
bool doit(int t,const int x,const int y,const int n)
{
    memset(dp,-1,sizeof(dp));
    dp[0] = 0;
    for(int ni = 1; ni <= n; ++ni)
    {
        if(dp[x] >= y) return true;
        int len = min(x, t/a[ni]);
        for(int i = x; i >= 0; --i)
        {
            for(int j = 0; j <= min(len, i); ++j)
            {
                if(dp[i-j] < 0) continue;
                dp[i] = max(dp[i],dp[i-j] + (t - j*a[ni])/b[ni]);
            }
        }
    }
    return dp[x] >= y;
}
int main()
{
    int cas;
    int n,x,y;
    scanf("%d",&cas);
    for(int cc = 1;cc <= cas;++cc){
        scanf("%d %d %d",&n,&x,&y);
        for(int i = 1; i <= n; ++i){
            scanf("%d %d",&a[i],&b[i]);
        }
        int ll = 1, rr = x*a[1] + y*b[1],mid = (ll + rr)/2;
        int ans;
        while(ll <= rr){
            if(doit(mid,x,y,n)){
                ans = mid;
                rr = mid - 1;
            }
            else
                ll = mid + 1;
            mid = (ll + rr)/2;
        }
        printf("Case %d: %d\n",cc,ans);
    }
    return 0;
}

参考:http://blog.csdn.net/vgo__/article/details/11284745