题解

35 条题解

  • 0
    @ 2018-04-07 17:22:26

      看起来题目变量非常多,其实想一想就能列出dp方程:f[i][j]f[i][j]表示第ii个机器人完成第jj个步骤,一共完成前jj个步骤所需要的最短时间;s[i][j]s[i][j]表示第ii个机器人做完前jj个步骤所需要的时间,那么:
    f[i][j]=min(f[k][l]+s[i][j]−s[i][l]+K)
    f[i][j]=min(f[k][l]+s[i][j]−s[i][l]+K)
      其中k∈[1,n]k∈[1,n]且k≠jk≠j,l∈[j−L,j−1]l∈[j−L,j−1]。

      但是这样的话复杂度有点高。。我们发现nn的范围只有5,我们可以从这里下手解决问题。如果对单独的一个机器人1号考虑,将dp方程转换一下:
    f[i][j]=min((f[1][l]−s[i][l])+s[i][j]+K)
    f[i][j]=min((f[1][l]−s[i][l])+s[i][j]+K)
      我们发现括号里的东西与j无关,可以用单调队列维护,所以我们开n个单调队列进行维护,问题就解决了。

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<queue> 
    #define MAXN 100005
    #define LL long long
    #define INF 2147483640
    #define MOD 100000007
    #define free(a) freopen("a.in","r",stdin);
    using namespace std;
    int m,n,kk,ll,t[10][MAXN],sum[10][MAXN],ans=MOD,f[10][MAXN];
    int main()
    {
        memset(f,0x3f,sizeof(f));
        scanf("%d%d%d%d",&m,&n,&kk,&ll);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&t[i][j]);
                sum[i][j]=sum[i][j-1]+t[i][j];
            }
        for(int i=0;i<=m;i++)
            f[0][i]=0;
        for(int i=0;i<=n;i++)
            f[i][0]=0;
        for(int j=1;j<=m;j++)
            for(int i=1;i<=n;i++)
                for(int l=j-ll;l<=j-1;l++)
                    for(int k=1;k<=n;k++)
                        if(k!=i)
                            f[i][j]=min(f[i][j],f[k][l]+sum[i][j]-sum[i][l]+kk);
        for(int i=1;i<=n;i++)
            ans=min(ans,f[i][m]);
        printf("%d",ans-kk);
        return 0;
    }
    
  • 0
    @ 2017-09-03 21:33:28

    首先,sum[i][j]表示第i台机器完成前j项任务所需的时间,f[i][j]表示完成了前i项任务,且第i项任务由第j台机器完成的最小时间,很容易写出转移方程:
    f[i][j]=minx=i−li−1f[x][p]+sum[j][i]−sum[j]x
    但是,这样转移的时间复杂度为O(nm2l)。

    考虑优化,进一步发现n很小,想办法从n下手优化:
    每一次转移如果 j 确定,找的是min(f[x][p]−sum[j][x])。可以建立n2个关于x的单调队列,且保证x,(f[x][p]−sum[j][x])单调递增。每次取队首更新即可。选取出的最优解再按单调队列的规则去更新其他单调队列。时间复杂度O(nm2)
    需要注意的一点是,要先把所有dp值算出来之后再一一更新。

  • 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;
    }

  • 0
    @ 2015-05-05 16:51:12

    测试数据 #0: Accepted, time = 31 ms
    测试数据 #1: Accepted, time = 62 ms
    测试数据 #2: Accepted, time = 31 ms
    测试数据 #3: Accepted, time = 93 ms
    测试数据 #4: Accepted, time = 109 ms
    测试数据 #5: Accepted, time = 375 ms
    测试数据 #6: Accepted, time = 546 ms
    测试数据 #7: Accepted, time = 531 ms
    测试数据 #8: Accepted, time = 703 ms
    测试数据 #9: Accepted, time = 890 ms
    Accepted, time = 3371 ms
    调用了deque……直接用数组模拟应该会快一点
    纪念队列优化第一题(觉得自己好水 (/▽╲))

  • 0
    @ 2015-04-04 11:05:03

    dp方程
    状态 d[i][j]表示执行了i个步骤,最后一个步骤使用机器j完成.
    转移 d[i][j]=min( d[j][v] + presum[i][j] + presum[p][j] +k ),
    其中presum[i][j]代表机器j的前i个步骤的执行时间总和,
    v代表上一次使用的机器(满足v!=j),
    p代表机器v最晚工作到的时间点(i-L<=p<i).
    对p这一维使用单调队列优化,或者线段树优化也行.
    可以直接用int.

  • 0
    @ 2012-07-26 15:33:00

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

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

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

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

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

    ├ 测试数据 06:运行时错误...|错误号: 216

    ├ 测试数据 07:答案错误...程序输出比正确答案长

    ├ 测试数据 08:运行超时...

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:运行超时...

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

    Unaccepted 有效得分:50 有效耗时:0ms

    大家懂的

  • 0
    @ 2009-11-08 12:10:13

    vijos数据比较弱

    我动规方程与下面rahangwei类似

    没有用单调队列 设了两个数组记录当前机器的前导最优解和取到该解的步骤

    当步骤不满足题意(与当前步骤距离超过l)时,枚举一次更新这两个数组

    照样0ms秒杀

  • 0
    @ 2009-11-04 14:39:56

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

    我的pas(仅供参考,copy无用):

    http://blog.sina.com.cn/s/blog_5774b8650100fv6o.html

  • 0
    @ 2009-10-21 13:20:24

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

    诧异了,第一次单调队列优化.....

    感谢楼下的思路,我绝对没有copy,同时发现你方程不小心写错了.还有f数组开[1..5]就够了~

  • 0
    @ 2009-10-19 13:20:21

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

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

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

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

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

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

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

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

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

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

    程序打得太残了。

    http://hi.baidu.com/think_exist

    有代码和稍微的解释。(直接copy没意义)

  • 0
    @ 2009-09-12 10:57:52

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    第一个单调队列

    纪念下

  • 0
    @ 2009-08-17 18:16:13

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-08-17 13:29:35

    大家注意

    第一次的K 不用加,所以要在输出哪里减去K

  • 0
    @ 2009-08-11 18:52:16

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

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

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

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

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

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

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

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

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

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

    单调队列优化

  • 0
    @ 2009-07-06 12:42:16

    装配线调度问题吧……

  • 0
    @ 2009-04-16 10:37:37

    唉~发现了~要先把5个队列函数值更新完再从单调队列里删点。。

    这题真是裸的单调队列啊。。难得连我都能做出的DP题

  • 0
    @ 2009-03-08 13:54:44

    裸着的单调队列。。

  • 0
    @ 2009-02-27 23:27:39

    太不容易了,细节很重要

  • 0
    @ 2009-02-26 18:12:53

    讨论中有我的题解,欢迎捧场。。。

  • 0
    @ 2009-01-12 15:39:16

    O(nnm)的双端队列,32行的程序调了两节课

    其实难度不大,但一不小心很容易就想庛了……

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

信息

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