https://vijos.org/p/1243
https://sea96.github.io/2017/02/25/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%9A%84%E5%90%84%E7%A7%8D%E4%BC%98%E5%8C%96/
https://blog.csdn.net/hahalidaxin/article/details/51017626
单调队列优化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]的最小值。
注意单调队列写法。
https://blog.csdn.net/XY20130630/article/details/51821751
设 f[i][j]f[i][j] 表示第 jj 个步骤由 ii 完成,而第 j+1j+1 个步骤不由 ii 完成。
则
f[i][j]=minnx=1(x≠i)minj−1Max(y=j−l,0)f[k][l]+∑m=l+1jT[i][m]
可用单调队列和前缀和进行优化
http://www.voidcn.com/article/p-pcchalxy-md.html
在经过一段时间的经营后,dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架,而要开始自己生产产品了!产品的生产需要M个步骤,每一个步骤都可以在N台机器中的任何一台完成,但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同,它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时,为了保证安全和产品的质量,每台机器最多只能连续完成产品的L个步骤。也就是说,如果有一台机器连续完成了产品的L个步骤,下一个步骤就必须换一台机器来完成。现在,dd_engi的OI商店有史以来的第一个产品就要开始生产了,那么最短需要多长时间呢?
某日Azuki.7对跃动说:这样的题目太简单,我们把题目的范围改一改
对于菜鸟跃动来说,这是个很困难的问题,他希望你能帮他解决这个问题
某日Azuki.7对跃动说:这样的题目太简单,我们把题目的范围改一改
对于菜鸟跃动来说,这是个很困难的问题,他希望你能帮他解决这个问题
格式
输入格式
第一行有四个整数M, N, K, L
下面的N行,每行有M个整数。第I+1行的第J个整数为T[J,I]。
下面的N行,每行有M个整数。第I+1行的第J个整数为T[J,I]。
输出格式
输出只有一行,表示需要的最短时间。
样例1
样例输入1
3 2 0 2
2 2 3
1 3 1
样例输出1
4
限制
1s
提示
对于50%的数据,N<=5,L<=4,M<=10000
对于100%的数据,N<=5, L<=50000,M<=100000
对于100%的数据,N<=5, L<=50000,M<=100000
来源
第一届“OI商店杯” dd_engi原创题目
https://sea96.github.io/2017/02/25/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%9A%84%E5%90%84%E7%A7%8D%E4%BC%98%E5%8C%96/
题意:产品的生产需要个步骤,每个步骤可以在个机器中任何一台完成,机器完成第个步骤的时间为。把半成品从一台机器上搬到另一台机器上也需要一定的时间,每台机器最多只能连续完成产品的个步骤,问最短需要多长时间。
题解:朴素的动态规划的算法:定义表示前i个步骤,最后一段步骤用第个机器完成,表示前个步骤用第个机器完成的时间。状态转移方程:
时间复杂度:。
把方程式变形得:
发现括号内的式子是根据决定的(枚举和),所以可以用单调队列维护一个单调递增的序列进行优化,时间复杂度:。
http://www.cnblogs.com/MashiroSky/p/5950893.html时间复杂度:。
把方程式变形得:
发现括号内的式子是根据决定的(枚举和),所以可以用单调队列维护一个单调递增的序列进行优化,时间复杂度:。
一个产品的生产有m个步骤,一共n个机器人。机器人i完成步骤j的时间为T[i][j],每次当产品从一个机器人那里移动到另一个机器人那里需要时间K,每个机器人不能持续工作L个步骤。问最少能在多少时间内完成。
看起来题目变量非常多,其实想一想就能列出dp方程:表示第个机器人完成第个步骤,一共完成前个步骤所需要的最短时间;表示第个机器人做完前个步骤所需要的时间,那么:
其中且,。
但是这样的话复杂度有点高。。我们发现的范围只有5,我们可以从这里下手解决问题。如果对单独的一个机器人1号考虑,将dp方程转换一下:
我们发现括号里的东西与j无关,可以用单调队列维护,所以我们开n个单调队列进行维护,问题就解决了。
int s[10][maxn],l[10],r[10],q[10][maxn],p[10][maxn],f[10][maxn]; int n,m,K,L; int main() { scanf ( "%d%d%d%d" ,&m,&n,&K,&L); for ( int i=1;i<=n;i++) for ( int j=1;j<=m;j++) scanf ( "%d" ,&s[i][j]),s[i][j]+=s[i][j-1]; for ( int i=1;i<=n;i++) l[i]=r[i]=1,q[i][1]=0,p[i][1]=0; for ( int j=1;j<=m;j++) { for ( int i=1;i<=n;i++) { while (l[i]<=r[i] && p[i][l[i]]<j-L) l[i]++; f[i][j]=q[i][l[i]]+s[i][j]+K; } for ( int i=1;i<=n;i++) for ( int k=1;k<=n;k++) if (k!=i) { while (l[k]<=r[k] && q[k][r[k]]>=f[i][j]-s[k][j]) r[k]--; q[k][++r[k]]=f[i][j]-s[k][j]; p[k][r[k]]=j; } } int ans=inf; for ( int i=1;i<=n;i++) ans=min(ans,f[i][m]); printf ( "%d" ,ans-K); return 0; } |
单调队列优化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]的最小值。
注意单调队列写法。
https://blog.csdn.net/XY20130630/article/details/51821751
设 f[i][j]f[i][j] 表示第 jj 个步骤由 ii 完成,而第 j+1j+1 个步骤不由 ii 完成。
则
f[i][j]=minnx=1(x≠i)minj−1Max(y=j−l,0)f[k][l]+∑m=l+1jT[i][m]
可用单调队列和前缀和进行优化
http://www.voidcn.com/article/p-pcchalxy-md.html
由于理论性的东西已经学过了,知道这是个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
这样就可以用单调队列实现了。