描述
在经过一段时间的经营后，dd_engi的OI商店不满足于从别的供货商那里购买产 品放上货架，而要开始自己生产产品了！产品的生产需要M个步骤，每一个步骤都可以在N台机器中的任何一台完成，但生产的步骤必须严格按顺序执行。由于这N 台机器的性能不同，它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的 时间K。同时，为了保证安全和产品的质量，每台机器最多只能连续完成产品的L个步骤。也就是说，如果有一台机器连续完成了产品的L个步骤，下一个步骤就必 须换一台机器来完成。现在，dd_engi的OI商店有史以来的第一个产品就要开始生产了，那么最短需要多长时间呢？
某日Azuki.7对跃动说:这样的题目太简单,我们把题目的范围改一改
对于菜鸟跃动来说,这是个很困难的问题,他希望你能帮他解决这个问题
格式
输入格式
第一行有四个整数M, N, K, L
下面的N行，每行有M个整数。第I+1行的第J个整数为T[J,I]。
输出格式
输出只有一行，表示需要的最短时间。
限制
1s
提示
对于50%的数据，N<=5，L<=4，M<=10000
对于100%的数据，N<=5， L<=50000，M<=100000
来源
第一届“OI商店杯” dd_engi原创题目
【思路】
单调队列优化DP。
设f[i][j]表示考虑到第i个步骤，且i步骤由j完成时的最小时间。有转移式：
f[i][j]=min{f[k][p]-sum[k][j]}+sum[i][j]，i-L<=k<=i-1
括号内的部分可以用n个单调队列维护。a[][]为辅助数组，
a[i][j]=min{f[i][k]}-sum[i][j]+K，1<=k<=m
表示f[i][j]时括号中可以取到的最小值，单调队列j维护区间[i-L,i-1]内a[][j]的最小值。
注意单调队列写法。
ps：这篇论文很适合入门：http://pan.baidu.com/s/1gexnMwj
【代码】
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 const int maxn = 200000+10; 7 const int INF = 1e9+1e9; 8 9 int L[6],R[6],q[maxn][6]; 10 int f[maxn][6] , a[maxn][6] , b[maxn][6]; 11 int n,m,K,lim; 12 13 void push(int i,int j) { 14 while(L[j]<R[j] && a[i][j]<=a[q[R[j]-1][j]][j]) R[j]--; 15 q[R[j]++][j]=i; 16 } 17 int pop(int i,int j) { 18 while(L[j]<R[j] && q[L[j]][j]<i-lim) L[j]++; 19 return a[q[L[j]][j]][j]; 20 } 21 int read(int& x) { 22 char c=getchar(); while(!isdigit(c))c=getchar(); 23 x=0; while(isdigit(c))x=x*10+c-'0',c=getchar(); 24 } 25 int main() { 26 read(n),read(m),read(K),read(lim); 27 for(int i=1;i<=m;i++) 28 for(int j=1;j<=n;j++) { 29 read(b[j][i]); 30 b[j][i]+=b[j-1][i]; 31 } 32 for(int j=1;j<=m;j++) push(0,j); 33 for(int i=1;i<=n;i++) 34 { 35 for(int j=1;j<=m;j++) 36 f[i][j]=pop(i,j)+b[i][j]; 37 for(int j=1;j<=m;j++) { //向单调队列中添加a[i][] 38 a[i][j]=INF; 39 for(int k=1;k<=m;k++) if(k!=j) 40 a[i][j]=min(a[i][j],f[i][k]); 41 a[i][j]=a[i][j]-b[i][j]+K; 42 push(i,j); 43 } 44 } 45 int ans=f[n][1]; 46 for(int i=1;i<=m;i++) ans=min(ans,f[n][i]); 47 printf("%d ",ans); 48 return 0; 49 }