分析：这是一种新姿势的dp。。。设f[i]表示a机器的使用时间还剩i的最小代价，这种用一个物品的状态来转移其他物品的dp第一次见。 那么明显有：f[j]=min(f[j],f[j-a[i]])用a做这次任务 f[j]=min(f[j],f[j]+b[i])用b做 f[j]=min(f[j],f[j-c[i]]+c[i])a,b一起做。 这其实就是个背包，总体积的话每次的最小代价加起来就是了。
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; int n,m; const int N=1e5+5; const int inf=1e9; int f[N],a[N],b[N],c[N]; int main() { scanf("%d",&n); fo(i,1,n) { scanf("%d%d%d",&a[i],&b[i],&c[i]); if (!a[i])a[i]=inf; if (!b[i])b[i]=inf; if (!c[i])c[i]=inf; int mx=inf; mx=min(min(mx,a[i]),min(b[i],c[i])); m+=mx; } fo(i,1,n) fd(j,m,0) { int t=inf; if (j-a[i]>=0) t=min(t,f[j-a[i]]); t=min(t,f[j]+b[i]); if (j-c[i]>=0)t=min(t,f[j-c[i]]+c[i]); f[j]=t; } int ans=inf; fo(i,0,m)ans=min(ans,max(i,f[i])); printf("%d\n",ans); }