首页 > 代码库 > [Vijos 1243]生产产品（单调队列优化Dp）
[Vijos 1243]生产产品（单调队列优化Dp）
Description
在经过一段时间的经营后，dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架，而要开始自己生产产品了！产品的生产需要M个步骤，每一个步骤都可以在N台机器中的任何一台完成，但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同，它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时，为了保证安全和产品的质量，每台机器最多只能连续完成产品的L个步骤。也就是说，如果有一台机器连续完成了产品的L个步骤，下一个步骤就必须换一台机器来完成。现在，dd_engi的OI商店有史以来的第一个产品就要开始生产了，那么最短需要多长时间呢？
某日Azuki.7对跃动说:这样的题目太简单,我们把题目的范围改一改
对于菜鸟跃动来说,这是个很困难的问题,他希望你能帮他解决这个问题
Solution
看了MashiroSky的题解=w=
f[j][i]表示完成了前i个步骤，第i步由j完成，预处理第j个机器完成前i个步骤的时间s[j][i]
考虑朴素的dp能得到转移方程f[j][i]=min(f[k][l]+s[j][i]-s[j][l]+K)=min(f[k][l]-s[j][l])+s[j][i]+K(l<i i-l<=L)
然后发现f[k][l]-s[j][l]与l有关 与i无关，此处可以单调队列优化，维护n个单调队列
就能O(mn2)解决啦
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#define N 6#define M 100005#define INF 0x3f3f3f3fusing namespace std;int m,n,k,L,t[N][M],f[N][M],q[N][M],p[N][M],l[N],r[N],ans=INF;int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f; }int main(){ m=read(),n=read(),k=read(),L=read(); for(int i=1;i<=n;i++) { l[i]=r[i]=1; for(int j=1;j<=m;j++) t[i][j]=read()+t[i][j-1]; } for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { while(l[j]<=r[j]&&q[j][l[j]]<i-L)l[j]++; f[j][i]=t[j][i]+p[j][l[j]]+k; } for(int k=1;k<=n;k++) { for(int j=1;j<=n;j++) { if(k==j)continue; while(l[j]<=r[j]&&p[j][r[j]]>=f[k][i]-t[j][i])r[j]--; q[j][++r[j]]=i; p[j][r[j]]=f[k][i]-t[j][i]; } } } for(int i=1;i<=n;i++)ans=min(f[i][m]-k,ans); printf("%d\n",ans); return 0;}
[Vijos 1243]生产产品（单调队列优化Dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。