洛谷 P2224 [HNOI2001]产品加工 题解【DP】【背包】【贪心】

作者: wjyyy 分类: DP,背包,解题报告,贪心 发布时间: 2018-06-29 15:36

点击量:82

 

   像这种进程DP也是第一次见,不过只要把所有状态列出来,想做还是有好办法的。

 

题目描述

某加工厂有A、B两台机器,来加工的产品可以由其中任何一台机器完成,或者两台机器共同完成。由于受到机器性能和产品特性的限制,不同的机器加工同一产品所需的时间会不同,若同时由两台机器共同进行加工,所完成任务又会不同。某一天,加工厂接到n个产品加工的任务,每个任务的工作量不尽一样。

 

你的任务就是:已知每个任务在A机器上加工所需的时间t1, B机器上加工所需的时间t2及由两台机器共同加工所需的时间t3,请你合理安排任务的调度顺序,使完成所有n个任务的总时间最少。

 

输入输出格式

输入格式:

(输入文件共n+1行)

 

第1行为 n。 n是任务总数(1≤n≤6000)

 

第i+1行为3个[0,5]之间的非负整数t1,t2,t3,分别表示第i个任务在A机器上加工、B机器上加工、两台机器共同加工所需要的时间。如果所给的时间t1或t2为0表示任务不能在该台机器上加工,如果t3为0表示任务不能同时由两台机器加工。

 

输出格式:

最少完成时间

 

输入输出样例

输入样例#1:
5
2 1 0
0 5 0
2 4 1
0 0 3
2 1 1
输出样例#1:
9
 

   我们首先看到,这个题同时维护两个甚至是三个进程,实在是不好想。我也是第一次看到有把数组下标当作最优状态求答案的,DP题见的应该还是越多越好。

 

   我们试着用f[i][j]来维护当前加工第i个物品,A机器用时为j时B机器的最短用时。①我们不用担心排序问题,②也不用担心同时做会耽误某个空档的时间。①因为我们把这个模型当作一个背包,只管加入工件,不管添加顺序(背包不也是这样么)。②同时做的后效性问题:因为这里做的时候不用排序,所以我们把所有加入背包的同时进行的进程提到最前面去。

 

   我们看这样一组数据:
3
5 0 0
0 2 0
0 0 3
   我们模拟这个过程,是这样的(分别编号为工件1,2,3)
   因为我们用的是背包,所以等价于下面这样:(贪心的思想)
   所以在没有顺序的时候,直接按背包做。我们的状态转移方程就是这样,不过状态只能单点转移而不是像背包那样只要比c[i]大都能转移:

 

   f[][]=∞ f[0][0]=0
   f[i][j]=min{f[i-1][j]+t2[i],f[i-1][j-t1[i]],f[i-1][j-t3[i]]+t3[i]}

 

   因为这个题数据范围达到\(5×6000^2=1.8\times 10^8\),超出1亿次,并且空间也会超128M,因此我们要优化枚举下界,并滚掉第一维。滚动比较好做,只要保存好转移t2时的状态,和背包相同。

 

   枚举下界的调整:我们可以看出,因为状态是非严格单调递增的,所以我们如果发现对∀i∈[0,k],f[i]=∞,那么k以下的状态已经作废了,不会再被用到。此时我们的枚举下界down就可以调整到k了,并且每次做完检验是否可以继续更新。

 

   同时要记得在输入的时候记录上界(up+=max{t1[i],t2[i],t3[i]}),并记得每次置为∞防止用到过时状态(尤其是做t2时可能会碰到两层前的状态)。

 

Code:(luogu开了O2才能过?)

#include<cstring>
#include<cstdio>
int f[30100];
int t[4][6666];
int max(int x,int y)//重载貌似比stl快一点
{
    return x>y?x:y;
}
int min(int x,int y)
{
    return x<y?x:y;
}
int main()
{
    memset(f,0x3f,sizeof(f));
    int n,up=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=3;j++)
            scanf("%d",&t[j][i]);
        up+=max(t[1][i],max(t[2][i],t[3][i]));
    }
    f[0]=0;
    int down=0,tmp;
    for(int i=1;i<=n;i++)
    {
        for(int j=up;j>=down;j--)
        {
            tmp=f[j];//初始化前存一下原来的值,但是只有t2能用(和其他题解不同)
            f[j]=0x3f3f3f3f;//相当于每次初始化
            if(j>=t[1][i]&&t[1][i]>0)
                f[j]=f[j]<f[j-t[1][i]]?f[j]:f[j-t[1][i]];
            if(j>=t[3][i]&&t[3][i]>0)
                f[j]=f[j]<f[j-t[3][i]]+t[3][i]?f[j]:f[j-t[3][i]]+t[3][i];
            if(t[2][i]>0)
                f[j]=f[j]<tmp+t[2][i]?f[j]:tmp+t[2][i];
        }
        while(f[down]>=0x3f3f3f3f)
            down++;
    }
    int ans=up;
    for(int i=down;i<=up;i++)
    {
        tmp=max(f[i],i);
        ans=ans<tmp?ans:tmp;
    }
    printf("%d\n",ans);
    return 0;
}

 

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
G_A_TS Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
G_A_TS
游客

%%%

/* */