软件公司

题目链接：http://acm.ocrosoft.com/problem.php?cid=1629&pid=55

题目描述：

一家软件开发公司有两个项目，并且这两个项目都由相同数量的m个子项目组成，对于同一个项目，每个子项目都是相互独立且工作量相当的。由于时效性，两个项目必须同时被完成，如果其中一个完成的早了，那么这两个项目都会无效。

这家公司有n名程序员分配给这两个项目，每个子项目必须由一名程序员一次完成，多名程序员可以同时做同一个项目中的不同子项目。

求公司完成两个项目的最少时间。

输入

第一行两个正整数n，m（1<=n<=100,1<=m<=100)。

接下来n行，每行包含两个整数，x和y。分别表示每个程序员完成第一个项目的子程序的时间，和完成第二个项目子程序的时间。每个子程序耗时也不超过100。

输出

包含一个整数，表示两个项目同时完成的时间

样例输入：
 

3 20
1 1
2 4
1 6

样例输出：

18

提示

【样例解释】

    第一个人做18个2项目，耗时18；第二个人做2个1项目，2个2项目耗时12；第三个人做18个1项目，耗时18。

【数据范围】

对于30%的数据，n<=30.

对于60%的数据，n<=60.

思路：二分减少时间复杂度，dp[i][j]代表到前i个人，在1项目做了j个的情况下，2项目能做的最多的个数。转移为：dp[i][j]=max{dp[i][j],dp[i-1][j-k]+(mid-k*a[i].x)/a[i].y

代码：

#include<bits/stdc++.h>
using namespace std;
struct people
{
	int x, y;//x为完成第一个项目的子程序的时间，y为完成第二个项目子程序的时间
}a[105];
int dp[105][105];
int main()
{
	int n, m;
	cin >> n >> m;//n个程序员m个子项目
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i].x >> a[i].y;
	}
	int left = 0;
	int right = 100;
	int mid;
	while (left < right)//二分查找答案
	{
		mid = (left + right) / 2;
		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j <= m; j++)
			{
				dp[i][j] = -999;
			}
		}
		dp[0][0] = 0;//初始化dp数组
		for (int i = 1; i <= n; i++)//每个人遍历
		{
			for (int j = 0; j <= m; j++)//每个1项目遍历
			{
				for (int k = 0; k <= j; k++)//第i个人完成0个到j个1项目的所有情况
				{
					if (mid - k * a[i].x < 0)break;//小于0，肯定时错误数据
					else
					{
						dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + (mid - k * a[i].x) / a[i].y);//状态转移方程，表示第i个人完成了总共j个1项目的同时最多可以完成几个2项目
					}
				}
			}
		}
		if (dp[n][m] >= m) { right = mid; }//只要完成的二项目大于二项目的子项目的个数，那这个时间就肯定对，继续二分
		else left = mid + 1;
	}
	cout << right << endl;

}