bzoj1222 [HNOI2001]产品加工

bzoj1222 [HNOI2001]产品加工

​​ Description

某加工厂有A、B两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。某一天，加工厂接到n个产品加工的任务，每个任务的工作量不尽一样。你的任务就是：已知每个任务在A机器上加工所需的时间t1, B机器上加工所需的时间t2及由两台机器共同加工所需的时间t3，请你合理安排任务的调度顺序，使完成所有n个任务的总时间最少。 Input

输入共n+1行第1行为 n。 n是任务总数（1≤n≤6000）第i+1行为3个[0，5]之间的非负整数t1,t2,t3，分别表示第i个任务在A机器上加工、B机器上加工、两台机器共同加工所需要的时间。如果所给的时间t1或t2为0表示任务不能在该台机器上加工，如果t3为0表示任务不能同时由两台机器加工。 Output

最少完成时间 Sample Input 5 2 1 0 0 5 0 2 4 1 0 0 3 2 1 1 Sample Output 9 唉又是个dp 再一次不会做了gg 膜了icefox巨佬的题解：设f[i]表示a机器做了i时长 b机器最小工作时长是多少 类似背包转移 枚举1~i个 然后从总容量上线开始往下枚举 分三种情况讨论哪种最少 最后统计答案即可

#include#include#include#define inf 0x3f3f3f3f#define N 33000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S)return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x;}int n,f[N],a[N],b[N],c[N];int main(){// freopen("bzoj1222.in","r",stdin); n=read();int sum=0; for (int i=1;i<=n;++i) { a[i]=read(),b[i]=read(),c[i]=read(); if (!a[i]) a[i]=inf;if (!b[i]) b[i]=inf;if (!c[i]) c[i]=inf; sum+=min(a[i],min(b[i],c[i])); }memset(f,0x3f,sizeof(f));f[0]=0; for (int i=1;i<=n;++i) for (int j=sum;~j;--j){ int tmp=inf;if (j>=a[i]) tmp=min(tmp,f[j-a[i]]); tmp=min(tmp,f[j]+b[i]);if (j>=c[i]) tmp=min(tmp,f[j-c[i]]+c[i]);f[j]=tmp; }int ans=inf; for (int i=0;i<=sum;++i) ans=min(ans,max(f[i],i));printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。