[HNOI2001]产品加工

题目链接

 [HNOI2001]产品加工

description

有机器甲乙二者,加工产品者也.今有(n)个产品,加工于甲需耗时间(t_{1}),加工于乙需耗时间(t_{2}),二者同时为其加工需耗时间(t_{3}).(若(t_{i})为(0),则表示无法用此方式加工)机器者,专一者也,一时只加工一产品也.试问加工完毕最小时间有几何.

solution

挺神奇的一道题.一开始考虑开三个数组(f[][3])表示利用三种方式加工所需最小时间,但不会转移.题解提供了一种非常神奇的状态表示方式.(f[i])表示甲加工时间为(i)时乙加工的最小时长,初始化为(inf).于是我们便可以进行转移:

$$ f[j]=b?f[j]+b:inf$$

$$if(a)   f[j]=min(f[j-a],f[j])$$

$$if(c)
f[j]=min(f[j],f[j-c]]+c)$$

参考马前卒前辈的代码初始化方式,只有90分,个人感觉是在初始化时间限制最大值的时候出错了吧.

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define R register
#define next mABlCDg
#define debug puts("mlg")
using namespace std;
const ll inf=((ull)1<<63-1);
ll n;
ll f[320000],Mxt;
ll ans;
int main(){
	n=read();
	for(R ll i=1;i<=319999;i++) f[i]=inf;
	f[0]=0;ans=inf;
	for(R ll i=1,a,b,c;i<=n;i++){
		a=read();b=read();c=read();
		Mxt+=max(a,max(b,c));
		for(R ll j=Mxt;j>=0;j--){
			if(b) f[j]+=b;
			else f[j]=inf;
			if(a&&j>=a) f[j]=min(f[j],f[j-a]);
			if(c&&j>=c) f[j]=min(f[j],f[j-c]+c);
		}
	}
	for(R ll i=0;i<=Mxt;i++) ans=min(ans,max(f[i],i));
	
	writeln(ans);
}