本文主要是介绍vijos 1243 生产产品 单调性优化动态规划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述 Description
在经过一段时间的经营后，dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架，而要开始自己生产产品了！产品的生产需要M个步骤，每一个步骤都可以在N台机器中的任何一台完成，但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同，它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时，为了保证安全和产品的质量，每台机器最多只能连续完成产品的L个步骤。也就是说，如果有一台机器连续完成了产品的L个步骤，下一个步骤就必须换一台机器来完成。现在，dd_engi的OI商店有史以来的第一个产品就要开始生产了，那么最短需要多长时间呢？
某日Azuki.7对跃动说:这样的题目太简单,我们把题目的范围改一改
对于菜鸟跃动来说,这是个很困难的问题,他希望你能帮他解决这个问题
输入格式 Input Format
第一行有四个整数M, N, K, L
下面的N行，每行有M个整数。第I+1行的第J个整数为T[I,J]。
输出格式 Output Format
输出只有一行，表示需要的最短时间。
样例输入 Sample Input
3 2 0 2
2 2 3
1 3 1
样例输出 Sample Output
4
时间限制 Time Limitation
1s
注释 Hint
对于50%的数据，N<=5，L<=4，M<=10000
对于100%的数据，N<=5， L<=50000，M<=100000
这道题是在看论文时看到的，于是到vijos那注册了一个账号来做做，谁知竟然做了一个下午，悲剧……
由于理论性的东西已经学过了，知道这是个dp+单调队列。可第一次编还是编了好久。
首先，很容易写出动态转移方程：f(i,j)=min( min( f(p,i) ) + sum(i,j) - sum(i,k) +val) ,i>k>i-l+1,m>p>0 && p!=i
由于m很小，小于6，所以，这个方程的主要优化在于寻找外层的min
而单调队列的方程为：f(x)= opt( cost[i] ) bound[x] <=i<x;
将动态转移方程化简得：f(i,j)=min( min( f(p,i) ) - sum(i,k) ) + sum(i,j)+val ,i>k>i-l+1,m>p>0 && p!=i
这样就可以用单调队列实现了。
View Code 
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<iostream> 4 #include<string> 5 #include<queue> 6 #include<deque> 7 #include<map> 8 #include<cmath> 9 #include<stack> 10 #include<algorithm> 11 #include<functional> 12 using namespace std; 13 const int N=6; 14 const int L=50010; 15 const int M=100010; 16 typedef __int64 LL; 17 struct TT{ 18 LL val; 19 int num; 20 TT(LL v,int n){val=v,num=n;}; 21 }; 22 deque<TT>que[N]; 23 LL sum[N][M]; 24 LL str[N][M]; 25 int l,n; 26 LL kk; 27 void init(){ 28 for(int i=0;i<n;i++){ 29 while(!que[i].empty()){ 30 que[i].pop_back(); 31 } 32 que[i].push_back(TT(0,-1)); 33 str[i][0]=sum[i][0]; 34 } 35 } 36 void update(int k){ 37 int first=0,second=0,now; 38 LL tmp; 39 if(str[0][k]>str[1][k])first=1; 40 else second=1; 41 42 for(int i=2;i<n;i++){ 43 if(str[i][k]<=str[first][k]){ 44 second=first,first=i; 45 }else{ 46 if(str[i][k]<str[second][k]){ 47 second=i; 48 } 49 } 50 } 51 52 for(int i=0;i<n;i++){ 53 now=first; 54 if(i==now){ 55 now=second; 56 } 57 tmp=str[now][k]-sum[i][k]+kk; 58 while(!que[i].empty() &&que[i].front().num+l<=k)que[i].pop_front(); 59 while(!que[i].empty() && que[i].back().val>=tmp)que[i].pop_back(); 60 que[i].push_back(TT(tmp,k)); 61 62 } 63 64 } 65 int main() 66 { 67 int m,i,j; 68 LL ans; 69 while(~scanf("%d%d%d%d",&m,&n,&kk,&l)){ 70 for(i=0;i<n;i++){ 71 scanf("%I64d",&sum[i][0]); 72 for(j=1;j<m;j++){ 73 scanf("%I64d",&sum[i][j]); 74 sum[i][j]+=sum[i][j-1]; 75 } 76 } 77 78 79 if(n==1){ 80 printf("%I64d\n",sum[0][m-1]); 81 }else{ 82 init(); 83 84 for(i=0;i<m;i++){ 85 for(j=0;j<n;j++){ 86 str[j][i]=que[j].front().val+sum[j][i]; 87 } 88 update(i); 89 } 90 m--; 91 ans=str[0][m]; 92 for(int i=1;i<n;i++){ 93 if(ans>str[i][m])ans=str[i][m]; 94 } 95 printf("%I64d\n",ans); 96 } 97 } 98 99 100 101 return 0; 102 } 103 /* 104 3 2 2 1 105 1 2 3 106 1 2 3 107 */
这篇关于vijos 1243 生产产品 单调性优化动态规划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
