HNOI2001 产品加工

题目传送门

思路蛮巧妙的，像我这种蒟蒻根本想不到是背包……

---

状态

用f[i]表示在(A)机器上用了时间(i)时，(B)机器所用的时间

转移

for(int i=1;i<=n;i++){
        int a=read(),b=read(),c=read();
		flag+=max(a,max(b,c));
        if(!a) a=1<<30; if(!b) b=1<<30; if(!c) c=1<<30; //如果不能在这台机器上加工，那么把它赋值为一个很大的数
        for(int j=flag;j>=0;j--){
            if(b==1<<30) dp[j]=b;
            else dp[j]+=b;
            //以上为赋初值——默认在B机器上加工
            //以下为状态转移
            if(j>=a) dp[j]=min(dp[j],dp[j-a]);
            if(j>=c) dp[j]=min(dp[j],dp[j-c]+c);
        }
    }

(code)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int read(){
    int k=0; char c=getchar();
    for(;c<'0'||c>'9';) c=getchar();
    for(;c>='0'&&c<='9';c=getchar())
      k=k*10+c-48;
     return k;
}
int dp[30010],flag;
int main(){
    int n=read();
    memset(dp,2,sizeof(dp)); dp[0]=0;
    for(int i=1;i<=n;i++){
        int a=read(),b=read(),c=read();
		flag+=max(a,max(b,c));
        if(!a) a=1<<30; if(!b) b=1<<30; if(!c) c=1<<30;
        for(int j=flag;j>=0;j--){
            if(b==1<<30) dp[j]=b;
            else dp[j]+=b;
            if(j>=a) dp[j]=min(dp[j],dp[j-a]);
            if(j>=c) dp[j]=min(dp[j],dp[j-c]+c);
        }
    }
    int ans=1<<30;
    for(int i=0;i<=flag;i++) ans=min(ans,max(dp[i],i));
    cout<<ans;
    return 0;
}