P1800 software_NOI导刊2010提高（06）

P1800 software_NOI导刊2010提高（06）

题目描述

一个软件开发公司同时要开发两个软件，并且要同时交付给用户，现在公司为了尽快完成这一任务，将每个软件划分成m个模块，由公司里的技术人员分工完成，每个技术人员完成同一软件的不同模块的所用的天数是相同的，并且是已知的，但完成不同软件的一个模块的时间是不同的，每个技术人员在同一时刻只能做一个模块，一个模块只能由一个人独立完成而不能由多人协同完成。一个技术人员在整个开发期内完成一个模块以后可以接着做任一软件的任一模块。写一个程序，求出公司最早能在什么时候交付软件。

---

我感觉oi中就就这么几种题目:

1.寻找答案题

2.带入答案检验题

3.数据结构题

4.完成某种目的的题

---

二分答案+dp检验

如果你感觉寻找答案不会的话。可以考虑二分答案

dp用的是背包

\(f[i]\)表示在干m天（m由二分得来）时干了i个第一个软件的模块时，干了多少个二软件的模块

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using std::max;

const int maxn=110;

int n,m;

int f[2][maxn];//填表法

int m1[maxn],m2[maxn];

bool check(int val)

{

	memset(f,0,sizeof(f));/每次清空

	f[0][0]=1;//初始化，为了不引起和无法到达的情况混淆的麻烦，都先加1.

	for(int i=1;i<=n;i++)

		for(int j=0;j<=m;j++)

		{

			f[i&1][j]=0;

			for(int k=0;k<=j&&val-k*m1[i]>=0;k++)//完全背包，不过不能用优化

				if(f[(i&1)^1][j-k])

					f[i&1][j]=max(f[i&1][j],f[(i&1)^1][j-k]+(val-k*m1[i])/m2[i]);

		}

	if(f[n&1][m]-1>=m)	return true;//这里要减1

	return false;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++)

		scanf("%d%d",&m1[i],&m2[i]);

	int l=1,r=20000;

	while(l<r)

	{

		int mid=(l+r)>>1;

		if(check(mid))

			r=mid;

		else

			l=mid+1;

	}

	printf("%d",l);

}