看起来题目变量非常多，其实想一想就能列出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;
}

首先，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: 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……直接用数组模拟应该会快一点
纪念队列优化第一题（觉得自己好水 (/▽╲)）

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.

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

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

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

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

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

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

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

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

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

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

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

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

大家懂的

vijos数据比较弱

我动规方程与下面rahangwei类似

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

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

照样0ms秒杀

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

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

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

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

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

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

├ 测试数据 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没意义）

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一个单调队列

纪念下

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

大家注意

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

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

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

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

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

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

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

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

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

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

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

单调队列优化

装配线调度问题吧……

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

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

裸着的单调队列。。

太不容易了，细节很重要

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

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

开N个单调队列保存N台机器从I-L到I的最优值..

对于一台机器T的某一个状态W,可以从另外N-1台机器的单调队列首过来,或者从本台机器单调队列的首或者第二个(如果队首元素的位置是I-L,这样的话第I个步骤就不能在本机上,所以直接取队列第2优的解)

但是只有一个点是L特别大的,感觉用这个优化都不值..