BZOJ1222_ 产品加工

题目传送门

我们设f[i]表示用机器A加工，时间还剩下i时的最优加工时间。

对于每一个时间可以加工的物品，有以下几个选择：

1、用机器A加工

2、用机器B加工

3、A和B一起加工

所以得到方程：

f[j]+=a[i][2]//用机器B加工，所以时间还剩j。

f[j]=min(f[j],f[j-a[i][1])(j>=a[i][1])//用机器A加工，所以由j-a[i][1]转移来。

f[j]=min(f[j],f[j-a[i][3]]+a[i][3])//用A、B一起加工，因为A也要出力，B也要出力，在减去a[i][3]的同时也要加上a[i][3]。

code:

/**************************************************************

    Problem: 1222

    User: yekehe

    Language: C++

    Result: Accepted

    Time:2084 ms

    Memory:1052 kb

****************************************************************/

#include <cstdio>

using namespace std;

inline int read(){

    char c;while(c=getchar(),(c<''||c>'')&&c!='-');int x=,y=;c=='-'?y=-:x=c-'';

    while(c=getchar(),c>=''&&c<='')x=x*+c-'';return x*y;

}

inline int min(int x,int y){return x<y?x:y;}

inline int max(int x,int y){return x>y?x:y;}

int n,a[][],f[];

int main(){

    n=read();

    int m=;

        for(int i=;i<=n;i++){

            a[i][]=read();a[i][]=a[i][]==?:a[i][];

            a[i][]=read();a[i][]=a[i][]==?:a[i][];

            a[i][]=read();a[i][]=a[i][]==?:a[i][];

            m+=min(min(a[i][],a[i][]),a[i][]);

        }

    f[]=;

        for(int i=;i<=n;i++){

            for(int j=m;j>=;j--){

                f[j]+=a[i][];

                if(j>=a[i][])f[j]=min(f[j],f[j-a[i][]]);

                if(j>=a[i][])f[j]=min(f[j],f[j-a[i][]]+a[i][]);

            }

        }

    int ans=;

        for(int i=;i<=m;i++)ans=min(ans,max(i,f[i]));

    printf("%d",ans);

}

巴特西

BZOJ1222_ 产品加工_KEY

最新文章

热门文章