BZOJ 1222 [HNOI2001]产品加工

题目大意

某加工厂有A、B两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。某一天，加工厂接到n个产品加工的任务，每个任务的工作量不尽一样。

你的任务就是：已知每个任务在A机器上加工所需的时间t1, B机器上加工所需的时间t2及由两台机器共同加工所需的时间t3，请你合理安排任务的调度顺序，使完成所有n个任务的总时间最少。

这道题听说是DP……我自己想出来啦哈哈哈哈哈

第一想法：$F_{i,j}$表示A机器工作i小时，B机器工作j小时能否生产X（变动ing）号货物

第二想法：$F_{i,j}$表示A机器工作i小时，产出j号货物B机器的最小工作时间。

后来发现第二维没必要建立啊qwq

所以最终状态就是$F_i$表示A机器工作i小时生产东西B机器最短的工作时间。之后每个东西类似于01背包尽姓处理就可以了。注意边界，判断条件中必须加入“如果i-1对其更新就用i更新，否则不更新这样的判断条件。”

之后状态就建立成功了。时间复杂度$O(T_{max} * N) \approx O(6000 * 30000)$

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,x[6010],y[6010],z[6010],f[30010],id[30010],ans=0x3f3f3f3f;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d%d%d",x+i,y+i,z+i);
	memset(f,0x3f,sizeof f);
	memset(id,-1,sizeof id);
	f[0]=0;
	id[0]=0;
	for(int i=1;i<=n;++i)
		for(int j=30000;~j;j--)
		{
			if(id[j]==i-1&&f[j]!=0x3f3f3f3f&&y[i]) f[j]+=y[i],id[j]=i;
			if(id[j-x[i]]==i-1&&f[j-x[i]]!=0x3f3f3f3f&&x[i]&&j>=x[i])
			{
				if(id[j]!=i) f[j]=f[j-x[i]];
				f[j]=min(f[j],f[j-x[i]]),id[j]=i;
			}
			if(id[j-z[i]]==i-1&&f[j-z[i]]!=0x3f3f3f3f&&z[i]&&j>=z[i])
			{
				if(id[j]!=i) f[j]=f[j-z[i]]+z[i];
				f[j]=min(f[j],f[j-z[i]]+z[i]),id[j]=i;
			}
		}
	for(int i=0;i<=30000;++i) if(id[i]==n) ans=min(ans,max(f[i],i));
	printf("%d\n",ans);
	return 0;
}