Description
某加工厂有(A)、(B)两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。某一天，加工厂接到n个产品加工的任务，每个任务的工作量不尽一样。
你的任务就是：已知每个任务在(A)机器上加工所需的时间(t_1),(B)机器上加工所需的时间(t_2)及由两台机器共同加工所需的时间(t_3)，请你合理安排任务的调度顺序，使完成所有(n)个任务的总时间最少。
Input
第(1)行为(n)。(n)是任务总数
第(i+1)行为(3)个([0，5])之间的非负整数(t_1,t_2,t_3)，分别表示第(i)个任务在(A)机器上加工、(B)机器上加工、两台机器共同加工所需要的时间。如果所给的时间(t_1)或(t_2)为(0)表示任务不能在该台机器上加工，如果(t_3)为(0)表示任务不能同时由两台机器加工。
Output
最少完成时间
Sample Input
5
2 1 0
0 5 0
2 4 1
0 0 3
2 1 1
Sample Output
9
Hint
(1~leq~n~leq~6000)
Solution
看过去这确实是个DP，但是状态难以设计。因为共有两个时间，无法将他们体现到一个最优值上去。但是考虑最大的用时是3e4，所以其中一个用时是可以枚举的，所以可以把用时放到状态中：由此可以设计出状态：
设(f_{i,j})为前i个任务，(A)机器花费(j)时间的(B)最小花费时间。方程显然：
(f_{i,j}=min){(f_{i-1,j-a},f_{i-1,j}+b,f_{i-1,j-c}+c)}
这样卡一卡常就过了（
Code
#include<cstdio>
#define rg register
#define ci const int
#define cl const long long int
typedef long long int ll;
namespace IO {
char buf[90];
}
template<typename T>
inline void qr(T &x) {
char ch=getchar(),lst=' ';
while(ch>'9'||ch<'0') lst=ch,ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(lst=='-') x=-x;
}
template<typename T>
inline void write(T x,const char aft,const bool pt) {
if(x<0) x=-x,putchar('-');
int top=0;
do {
IO::buf[++top]=x%10+'0';
x/=10;
} while(x);
while(top) putchar(IO::buf[top--]);
if(pt) putchar(aft);
}
template<typename T>
inline T mmax(const T a,const T b) {return a>b?a:b;}
template<typename T>
inline T mmin(const T a,const T b) {return a<b?a:b;}
template<typename T>
inline T mabs(const T a) {return a<0?-a:a;}
template<typename T>
inline void mswap(T &a,T &b) {
T temp=a;a=b;b=temp;
}
const int maxn = 6010;
const int maxm = 30010;
int frog[maxm];
int main() {
rg int n=0;qr(n);
rg int a,b,c;
for(rg int i=1;i<=n;++i) {
a=b=c=0;qr(a);qr(b);qr(c);
if(!a) a=maxm;if(!b) b=maxm;if(!c) c=maxm;
for(rg int j=30000;~j;--j) {
frog[j]+=b;
if(j >= a) frog[j]=mmin(frog[j],frog[j-a]);
if(j >= c) frog[j]=mmin(frog[j],frog[j-c]+c);
}
}
rg int ans=0x3f3f3f3f;
for(rg int i=0;i<30001;++i) {
ans=mmin(ans,mmax(frog[i],i));
}
write(ans,'
',true);
return 0;
}
Summary
当一个状态的最优值包括(n)个参数时，可以将(n-1)个参数放到状态中，每次转移为其他参数为该状态时，剩下参数的最值。最后枚举参数求得答案。