首页 > 其他 > 详细

HNOI2001 产品加工

时间:2018-11-02 21:05:02      阅读:136      评论:0      收藏:0      [点我收藏+]

链接 P2224[HNOI2001]产品加工

  • noip刷水题系列
  • \(ycb\)的套路,把答案压到状态里,设\(f_{i,j}\)表示当前在处理\(i\)个工作,\(a\)的时间为\(j\)\(b\)时间最小值。
  • 这样就不需要考虑工作的排序了,直接转移即可。
  • 正确性?因为考虑工作排序的原因是某个人一直在等另外一个,但是我们可以贪心的把一起要做的工作最开始全部做掉,这样后面的决策两个人都是独立的了。
  • 所以出题人为什么\(n\leq 6*10^3\),感觉复杂度还是有点假。
#include<bits/stdc++.h>
#define R register int 
using namespace std;
const int N=6001;
int n,ans,a[N],b[N],c[N],tot[N],f[2][N*10];
int gi(){
    R x=0,k=1;char c=getchar();
    while(c!=‘-‘&&(c<‘0‘||c>‘9‘))c=getchar();
    if(c==‘-‘)k=-1,c=getchar();
    while(c>=‘0‘&&c<=‘9‘)x=(x<<3)+(x<<1)+c-‘0‘,c=getchar();
    return x*k;
}
int main(){
    n=gi(),ans=1e9;
    for(R i=1;i<=n;++i){
        a[i]=gi(),b[i]=gi(),c[i]=gi();
        tot[i]=tot[i-1]+max(a[i],max(b[i],c[i]));
    }
    R now=0,pre=1;memset(f,0x7f,sizeof(f));
    f[now][0]=0;
    for(R i=1;i<=n;++i){
        now^=1,pre^=1;
        memset(f[now],0x7f,sizeof(f[now]));
        for(R j=0;j<=tot[i];++j){
            if(j>=a[i]&&a[i])f[now][j]=min(f[pre][j-a[i]],f[now][j]);
            if(b[i])f[now][j]=min(f[now][j],f[pre][j]+b[i]);
            if(j>=c[i]&&c[i])f[now][j]=min(f[pre][j-c[i]]+c[i],f[now][j]);
        }
    }
    for(R i=0;i<=tot[n];++i)
        ans=min(ans,max(i,f[now][i]));
    cout<<ans<<endl;
    return 0;
}

HNOI2001 产品加工

原文:https://www.cnblogs.com/Tyher/p/9898234.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!