题解

35 条题解

  • 1
    @ 2008-11-08 14:59:32

    优化方程f[i]=min(f[k]+cost);

    递推的时候,一旦计算出f[i],就把f[i]-cost进线段树。决策的时候f[i]=线段树中最小的值+cost,时间优化为O(NLOGN)

  • 1
    @ 2008-11-08 10:19:06

    思想:先考虑朴素的动态规划,可以很容易的找出动态转移方程。定义F为生产前I个产品,最后一个在J上生成的最优值,所以F:=Min{F[K,P]+W+Cost,F[K,J]+Cost}。但是,这个是四重循环,在数据很大的情况下,很容易的就会超时。那么,我们来考虑优化。

    优化1:保留每一个阶段的最优值和次优值,这样,就很不用再循环上述中的P了。(不过此题P的范围为5,所以可以忽略此优化)

    优化2:构造优先队列。由于有最大长度L的限制,所以这个题很棘手。我们再来定义一个状态,G为生产前I个产品,最有一个在J上生成的最优值,但是,规定G必须是从上一个不一样的工厂转移过来的,换一句话说,这个产品是在L长度内,以J号工厂为起点的第一个产品。所以我们可以得出F:=G+Sum-Sum。由于G和Sum随着T的不同是变化的,但是这个变化会产生一个最优的变化,所以我们定义一个在工厂J的优先队列Que,tail为其尾,head为其头,所以我们将G-Sum这个值加入这个工厂的优先队列,这样,每次取值就可以在O(1)的时间内解决。还有一个注意的,如果队首已经到现在这个点,已经超过L这个长度,则要把头递增1。

  • 1
    @ 2008-09-27 17:17:43

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 259ms

    ├ 测试数据 08:答案正确... 509ms

    ├ 测试数据 09:答案正确... 588ms

    ├ 测试数据 10:答案正确... 509ms

    貌似这里就是我最慢....我是用N*M*LOG(L)做的,虽然没人家快,毕竟是第一次写队列优化,自喜一下

    具体的就是用F表示第I个机器做第J个工序的最小时间

    G表示第I个机器做第J个工序且上个工序机器不同的最小时间

    用一个N个堆表示每个机器I在做某一个步骤J的时候,G..G的值

    所以F:=HEAP.DT+K+SUM(HEAP[P,1].P..J);

    为了方便,堆里记的是G-SUM;

    所以F:=HEAP.DT+K+SUM[1..J];

    还有一点,就是我WA了N次的点,就是第4点L=1,大家注意一下啊

  • 1
    @ 2008-08-13 21:53:49

    整整一天啊!!!!!!!!

    终于 AC 了!!!!!!!

    但是队列还是不太明白????????

  • 1
    @ 2007-11-12 15:59:22

    晕了,什么时候才能掌握队列优化??

  • 1
    @ 2007-11-07 16:29:01

    =.=

    晕了..被一个超级SB的错误困扰了一下午..

  • 1
    @ 2007-09-28 19:05:44

    额。。。自己想出来一次过的

    队列优化?不错的名字~~

  • 1
    @ 2007-09-18 19:42:56

    Accepted 有效得分:100 有效耗时:278ms

    终极猥琐的方法`\先鄙视下自己

    不过还是过了 呵呵~

  • 1
    @ 2007-07-22 21:58:16

    本题情况

    本人提交前:通过34人 提交360次 通过率9%

    提交AC后:通过35人 提交361次 通过率10%

  • 1
    @ 2007-07-20 09:36:05

    ft...搞了那么久,原来是数组开小了………………

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 9ms

    ├ 测试数据 10:答案正确... 41ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:50ms

    什么是队列优化???我可没用。。。直接O(NNM)的dp...

  • 1
    @ 2007-07-17 15:11:20

    明显的队列优化~~~~

    哈哈, 一次AC!!

  • 1
    @ 2007-06-05 22:03:26

    此题乍看很简单,细数数据便犯难

    动规队列一优化,一秒谁都能算完

  • 1
    @ 2007-05-15 08:30:02

    DP

    稍微优化一下

    用不着单调队列

  • 1
    @ 2006-10-14 16:26:15

    请问这单调队列用什么数据结构实现?

  • 0
    @ 2015-11-02 16:29:04

    转移方程为: f[i][j]=min( f[t][p]+sum[j][i]-sum[p][j]) 化简后可以得到 f[i][j]=min( f[t][p]-sum[p][j])+sum[j][i] 对于每一个j考虑开一个单调队列优化 ,维护 t和f[t][p]-sum[p][j]单调递增。这样每次从队首取出符合要求的一个即可更新.
    q[a][x][0]表示队列中这个位置的的t q[a][x][1]表示这个位置的p

    每次先更新所有的f[i][j]然后再更新所有的队列q[k] <j!=k> 刚开始0入队 最后减掉多增加的一组cost

    更详细的解答可以看这篇论文 《用单调性优化动态规划》http://www.docin.com/p-49960245.html
    #include <cstdio>
    #include <algorithm>
    #include <deque>
    #include <cstring>
    using namespace std;
    const int N=100010,INF=2099999999;
    int q[10][N][2],l[10],r[10];
    int m,n,cost,L,sum[10][N],f[N][10],ans=INF;
    int main(){
    freopen("1243.in","r",stdin);freopen("1243.out","w",stdout);
    scanf("%d%d%d%d",&m,&n,&cost,&L);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) scanf("%d",&sum[i][j]),sum[i][j]+=sum[i][j-1];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) f[j][i]=INF;
    for(int i=1;i<=n;i++) q[i][ r[i]++ ][0]=0;

    for(int i=1;i<=m;i++){
    for(int k=1;k<=n;k++){
    while(l[k]<r[k] && i-q[k][ l[k] ][0]>L) l[k]++;
    int t=q[k][ l[k] ][0],p=q[k][ l[k] ][1];
    f[i][k]=min(f[i][k],f[t][p]+sum[k][i]-sum[k][t]+cost);
    }
    for(int k=1;k<=n;k++)
    for(int j=1;j<=n;j++)//用f[i][k] 的值来更新 q[j];
    if(j!=k) {
    while(l[j]<r[j] && f[i][k]-sum[j][i]<= f[ q[j][r[j]-1][0] ][q[j][r[j]-1][1]] - sum[j][q[j][r[j]-1][0]]) r[j]--;
    q[j][r[j]][0]=i;q[j][r[j]++][1]=k;
    }
    }
    for(int i=1;i<=n;i++) ans=min(ans,f[m][i]);
    printf("%d",ans-cost);
    return 0;
    }

信息

ID
1243
难度
8
分类
动态规划 | 单调性DP 点击显示
标签
(无)
递交数
2571
已通过
360
通过率
14%
被复制
4
上传者