POJ1793&&EOJ21 Software Company

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 864		Accepted: 348

Description

A software developing company has been assigned two programming projects. As both projects are within the same contract, both must be handed in at the same time. It does not help if one is finished earlier.

This company has n employees to do the jobs. To manage the two projects more easily, each is divided into m independent subprojects. Only one employee can work on a single subproject at one time, but it is possible for two employees to work on different subprojects of the same project simultaneously.

Our goal is to finish the projects as soon as possible.

Input

The first line of the input file contains a single integer t (1 <= t <= 11), the number of test cases, followed by the input data for each test case. The first line of each test case contains two integers n (1 <= n <= 100), and m (1 <= m <= 100). The input for this test case will be followed by n lines. Each line contains two integers which specify how much time in seconds it will take for the specified employee to complete one subproject of each project. So if the line contains x and y, it means that it takes the employee x seconds to complete a subproject from the first project, and y seconds to complete a subproject from the second project.

Output

There should be one line per test case containing the minimum amount of time in seconds after which both projects can be completed.

Sample Input

Sample Output

*********************************************************

题目大意：一个公司要生产两种软件，现在每种软件有m个。有n个员工，第i个员工做一个软件a要a[i]的时间，做一个软件b要b[i]的时间，问做完全部的软件最少需要的时间。

解题思路：二分答案+dp背包；

网上都这么说。表示dp我学艺不精，一开始还真没想到该dp，当看到别人说这道题是dp的时候，心拔凉拔凉的，自以为对dp还算比较了解的我= =没想出来该怎么dp。这道题有几个纠结的地方：1.人员怎么分配；2.要dp的话，dp的状态是什么，下小标是什么，dp数组保存的是什么，根据什么dp；3.感觉变量好多还是相互联系的。

没办法，参考了网上的众多结题报告才明白是怎么回事。dp[i][j]表示在tim的时间内前i个员工做了a软件j个之后所能做的b软件的最大值，dp里面的是b软件的最大值，那个tim是二分时间得来的。可以想得通：当tim增加的时候，dp[i][j]一定是不减的，所以可以二分时间。当dp[n][m]>=m也就是n个员工在tim的时间内做了m个a软件以及超过m的b软件，所以，假定的时间tim就可以缩小。至于dp[i][j]的状态转移：

dp[i][j]=max{dp[i][j],dp[i-1][j-k]+(tim-k*a[i])/b[i]};这个方程也是网上共有的。(tim-k*a[i])/b[i]表示分配给第i个员工k件a软件然后在tim时间内做完的b软件的个数。这个状态转移，说实话，一开始没想通，的确很妙。

二分答案，把时间这个变量固定下来，dp第一维，把员工变量固定下来，dp第二维，把a软件的制作个数固定下来，dp的内容，来验证二分答案的正确性。完美啊。

#include <stdio.h>
#include <string.h>
#include <vector>
#define N 105
#define INF 0x3f3f3f3f
using namespace std;

int n,m,maxx;
int a[N],b[N];
int dp[N][N];

int ok(int tim)
{
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=m;i++)
        if(i*a[1]<=tim)
            dp[1][i]=(tim-i*a[1])/b[1];
        else break;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
            for(int k=0;k<=j&&a[i]*k<=tim;k++)
                if(dp[i-1][j-k]!=-1)
                    dp[i][j]=max(dp[i][j],dp[i-1][j-k]+(tim-k*a[i])/b[i]);
    }
    return  dp[n][m]>=m;
}

void re(void)
{
    maxx=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        maxx=max(a[i],maxx);
        maxx=max(b[i],maxx);
    }
}

void run(void)
{
    int le=0,ri=maxx*m*2,mid;
    while(mid=(le+ri)/2,le<ri)
    {
        if(ok(mid))ri=mid;
        else           le=mid+1;
    }
    printf("%d\n",ri);
}

int main()
{
    int ncase;
    scanf("%d",&ncase);
    while(ncase--)
    {
        re();
        run();
    }
    return 0;
}