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.?
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
*********************************************************
題目大意：一個公司要生產兩種軟件，現在每種軟件有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;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
