Description

Input

Output

Sample Input

    
      1

3 20

1 1

2 4

1 6


    
  

Sample Output

    
      18
    
  

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

    
      題目大意：一個公司要生產(chǎn)兩種軟件，現(xiàn)在每種軟件有m個。有n個員工，第i個員工做一個軟件a要a[i]的時間，做一個軟件b要b[i]的時間，問做完全部的軟件最少需要的時間。
    
  

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

    
      網(wǎng)上都這么說。表示dp我學藝不精，一開始還真沒想到該dp，當看到別人說這道題是dp的時候，心拔涼拔涼的，自以為對dp還算比較了解的我= =沒想出來該怎么dp。這道題有幾個糾結的地方：1.人員怎么分配；2.要dp的話，dp的狀態(tài)是什么，下小標是什么，dp數(shù)組保存的是什么，根據(jù)什么dp；3.感覺變量好多還是相互聯(lián)系的。
    
  

    
      沒辦法，參考了網(wǎng)上的眾多結題報告才明白是怎么回事。dp[i][j]表示在tim的時間內(nèi)前i個員工做了a軟件j個之后所能做的b軟件的最大值，dp里面的是b軟件的最大值，那個tim是二分時間得來的?？梢韵氲猛ǎ寒攖im增加的時候，dp[i][j]一定是不減的，所以可以二分時間。當dp[n][m]>=m也就是n個員工在tim的時間內(nèi)做了m個a軟件以及超過m的b軟件，所以，假定的時間tim就可以縮小。至于dp[i][j]的狀態(tài)轉(zhuǎn)移：
    
  

    
      dp[i][j]=max{dp[i][j],dp[i-1][j-k]+(tim-k*a[i])/b[i]};這個方程也是網(wǎng)上共有的。(tim-k*a[i])/b[i]表示分配給第i個員工k件a軟件然后在tim時間內(nèi)做完的b軟件的個數(shù)。這個狀態(tài)轉(zhuǎn)移，說實話，一開始沒想通，的確很妙。
    
  

    
      二分答案，把時間這個變量固定下來，dp第一維，把員工變量固定下來，dp第二維，把a軟件的制作個數(shù)固定下來，dp的內(nèi)容，來驗證二分答案的正確性。完美啊。
    
  

      #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;

}


    

POJ1793&&EOJ21 Software Company