亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

POJ1793&&EOJ21 Software Company

系統(tǒng) 1779 0
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

    
      1

3 20

1 1

2 4

1 6


    
  

Sample Output

    
      18
    
  
    
      *********************************************************
    
  
    
      題目大意:一個(gè)公司要生產(chǎn)兩種軟件,現(xiàn)在每種軟件有m個(gè)。有n個(gè)員工,第i個(gè)員工做一個(gè)軟件a要a[i]的時(shí)間,做一個(gè)軟件b要b[i]的時(shí)間,問做完全部的軟件最少需要的時(shí)間。
    
  
    
      解題思路:二分答案+dp背包;
    
  
    
      網(wǎng)上都這么說。表示dp我學(xué)藝不精,一開始還真沒想到該dp,當(dāng)看到別人說這道題是dp的時(shí)候,心拔涼拔涼的,自以為對(duì)dp還算比較了解的我= =沒想出來該怎么dp。這道題有幾個(gè)糾結(jié)的地方:1.人員怎么分配;2.要dp的話,dp的狀態(tài)是什么,下小標(biāo)是什么,dp數(shù)組保存的是什么,根據(jù)什么dp;3.感覺變量好多還是相互聯(lián)系的。
    
  
    
      沒辦法,參考了網(wǎng)上的眾多結(jié)題報(bào)告才明白是怎么回事。dp[i][j]表示在tim的時(shí)間內(nèi)前i個(gè)員工做了a軟件j個(gè)之后所能做的b軟件的最大值,dp里面的是b軟件的最大值,那個(gè)tim是二分時(shí)間得來的。可以想得通:當(dāng)tim增加的時(shí)候,dp[i][j]一定是不減的,所以可以二分時(shí)間。當(dāng)dp[n][m]>=m也就是n個(gè)員工在tim的時(shí)間內(nèi)做了m個(gè)a軟件以及超過m的b軟件,所以,假定的時(shí)間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]};這個(gè)方程也是網(wǎng)上共有的。(tim-k*a[i])/b[i]表示分配給第i個(gè)員工k件a軟件然后在tim時(shí)間內(nèi)做完的b軟件的個(gè)數(shù)。這個(gè)狀態(tài)轉(zhuǎn)移,說實(shí)話,一開始沒想通,的確很妙。
    
  
    
      二分答案,把時(shí)間這個(gè)變量固定下來,dp第一維,把員工變量固定下來,dp第二維,把a(bǔ)軟件的制作個(gè)數(shù)固定下來,dp的內(nèi)容,來驗(yàn)證二分答案的正確性。完美啊。
    
  
      #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


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 天天干天天射综合网 | 狠狠色综合色综合网络 | 亚洲精品久久久午夜伊人 | 国产综合欧美日韩视频一区 | 香蕉视频免费在线观看 | 老子影院午夜精品欧美视频 | 亚洲精品一区二区中文 | 在线免费国产视频 | 亚洲国产综合久久精品 | 手机福利在线观看 | 国产区二区 | 欧美高清性粉嫩交 | 国产精品18久久久久久小说 | 久久中文娱乐网 | 俄罗斯一级毛片免费视频 | 国产精品乱码免费一区二区 | 亚欧在线视频 | 国产高清看片日韩欧美久久 | 国产成人91高清精品免费 | 国产伦一区二区三区四区久久 | 亚洲国产精品久久久久网站 | 久久精品免费视频6 | 亚洲另类图 | 天天爽夜夜爽天天做夜夜做 | 97色97色97色成人 | 欧美中文字幕在线观看 | 夜夜爱夜夜操 | 大美女久久久久久j久久 | 五月婷婷综合在线视频 | 在线观看av片永久免费 | 激情婷婷综合 | 狠狠色噜噜狠狠狠狠色吗综合 | 欧美在线一区二区三区 | 99精品国产成人a∨免费看 | 日韩精品一区二区三区免费观看 | 中文国产成人精品少久久 | 香港三级做爰大爽视频 | 爱爱视频天天看 | 美女狠狠干| 亚洲国产一区二区三区综合片 | 中文字幕视频免费 |