用w[i]表示在A中用了i的时间时在B中最少用多长时间，然后转移就可以了。
备注：这个边界不好定义，所以可以每次用一个cur来存储最优值，然后对w[i]赋值就可以了。
/************************************************************** Problem: 1222 User: BLADEVIL Language: C++ Result: Accepted Time:2648 ms Memory:992 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #include <cstring> #include <algorithm> #define maxn 6010 #define inf (~0U>>2) using namespace std; int n,m; int a[maxn],b[maxn],c[maxn]; int w[maxn*5]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for (int i=1;i<=n;i++) { if (!a[i]) a[i]=inf; if (!b[i]) b[i]=inf; if (!c[i]) c[i]=inf; m+=min(a[i],min(b[i],c[i])); } for (int i=1;i<=n;i++) for (int j=m;j>=0;j--) { int cur(inf); if (b[i]!=inf) cur=w[j]+b[i]; if (j>=a[i]) cur=min(cur,w[j-a[i]]); if (j>=c[i]) cur=min(cur,w[j-c[i]]+c[i]); w[j]=cur; } int ans(inf); for (int i=1;i<=m;i++) ans=min(ans,max(i,w[i]));//printf("%d ",w[i]); printf("%d\n",ans); return 0; }
update：又仔细想了想这道题，发现其实是可以不用cur的，我们只需要每次假设当前i这个物品在某个机器上加工了，然后再不断更新就可以了。不知道哪里可能会溢出，所以将inf的值改小就可以了。
/************************************************************** Problem: 1222 User: BLADEVIL Language: C++ Result: Accepted Time:2100 ms Memory:992 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #include <cstring> #include <algorithm> #define maxn 6010 #define inf (30010) using namespace std; int n,m; int a[maxn],b[maxn],c[maxn]; int w[maxn*5]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]); for (int i=1;i<=n;i++) { if (!a[i]) a[i]=inf; if (!b[i]) b[i]=inf; if (!c[i]) c[i]=inf; m+=min(a[i],min(b[i],c[i])); } for (int i=1;i<=n;i++) for (int j=m;j>=0;j--) { w[j]=w[j]+b[i]; if (j>=a[i]) w[j]=min(w[j],w[j-a[i]]); if (j>=c[i]) w[j]=min(w[j],w[j-c[i]]+c[i]); } int ans(inf); for (int i=1;i<=m;i++) ans=min(ans,max(i,w[i]));//printf("%d ",w[i]); printf("%d\n",ans); return 0; }
原文：http://www.cnblogs.com/BLADEVIL/p/3715685.html