题面描述
某加工厂有A、B两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。某一天，加工厂接到n个产品加工的任务，每个任务的工作量不尽一样。你的任务就是：已知每个任务在A机器上加工所需的时间t1, B机器上加工所需的时间t2及由两台机器共同加工所需的时间t3，请你合理安排任务的调度顺序，使完成所有n个任务的总时间最少。
输入格式
输入共n+1行第1行为 n。 n是任务总数（1≤n≤6000）第i+1行为3个[0，5]之间的非负整数t1,t2,t3，分别表示第i个任务在A机器上加工、B机器上加工、两台机器共同加工所需要的时间。如果所给的时间t1或t2为0表示任务不能在该台机器上加工，如果t3为0表示任务不能同时由两台机器加工。
输出格式
最少完成时间
样例输入1
5
2 1 0
0 5 0
2 4 1
0 0 3
2 1 1
样例输出1
9
题解
比一般DP更加复杂一些，但是只要有了灵感依然十分容易做出来。对于每一个物品i，我们设f[i][j]表示当A机器使用时间为j的时候B机器使用的时间，这里不需要考虑同时在A和B上一起做的所需时间，因为我们可以将其一般化为同时满足在A上做且在B上做，也就与前一种情况相同了。当然，要注意用滚动数组把二维的DP转化为一维的，不然会导致MLE
#include<bits/stdc++.h>
#define maxn 30005
#define inf 0x3f3f3f3f
using namespace std;
inline char get(){
static char buf[300],*p1=buf,*p2=buf;
return p1==p2 && (p2=(p1=buf)+fread(buf,1,300,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
register char c=get();register int f=1,_=0;
while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
return _*f;
}
int f[maxn];
int n;
int a,b,a_b,sum=0;
int get_ans(int a,int b,int c){
return min(a,max(b,c));
}
int main(){
//freopen("1.txt","r",stdin);
n=read();
for(register int i=0;i<maxn;i++)f[i]=0x3f3f3f3f;
f[0]=0;
for(register int i=1;i<=n;i++){
a=read();b=read();a_b=read();
sum+=max(a,max(b,a_b));
for(register int j=sum;j>=0;j--){
if(b)f[j]+=b;
else f[j]=inf;
if(a_b && j>=a_b)f[j]=min(f[j],f[j-a_b]+a_b);
if(a && j>=a)f[j]=min(f[j],f[j-a]);
}
}
int ans=inf;
for(register int i=0;i<=sum;i++)ans=get_ans(ans,i,f[i]);
printf("%d
",ans);
return 0;
}