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

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

思想：先考虑朴素的动态规划，可以很容易的找出动态转移方程。定义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。

编译通过...

├ 测试数据 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,大家注意一下啊

整整一天啊！！！！！！！！

终于 AC 了！！！！！！！

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

晕了，什么时候才能掌握队列优化？？

=.=

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

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

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

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

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

不过还是过了 呵呵~

本题情况

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

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

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...

明显的队列优化~~~~

哈哈, 一次AC!!

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

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

DP

稍微优化一下

用不着单调队列

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

转移方程为: 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;
}