LINK

题意：有1个产品，m个步骤编号为1~m。步骤要在n个机器人的手中生产完成。其中，第i个步骤在第j个机器人手中的生产时间给定为$T[i][j]$，切换机器人消耗cost。步骤必须按顺序，同一个机器人不能连续完成超过l个步骤。求完成所有步骤的最短时间是多少。其中$m<=10^5$，$n<=5$，$l<=5*10^4$

思路：这题用DP考虑易得一个转移方程$dp[i][j]=\min^{i-1}_{v=i-L}{(dp[v][x] + sum[i][j] - sum[v][j]) + cost}$其中$sum[i][j]$代表前i步由j完成的时间和

从转移式上来看，j为要转移到的状态，x为出发态，相当于对每个步骤v都做$O(n^2)$的转移，直接暴力枚举的话总复杂度是$O(l·m·n^2)$

当L足够大时，显然这样的算法不够快，可以注意到v的枚举是顺序的，而且$dp[v][x] -sum[v][j]$在给定x和j时也满足单调性的要求，即当$dp[v][x] -sum[v][j]$得到更小的值后，最优值为新得到的值，那么使用二维优先队列维护从x机器人转移到j机器人，范围为L的优先队列，队列存储其划分的位置，这样一来我们可在$O(1)$复杂度内获得L范围内的最小值（队列中元素最多进出一次），优化后复杂度$O(m·n^2)$

/** @Date    : 2017-07-19 19:25:11  * @FileName: vijos 1243 单调性优化 DP 双端队列.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;int n, m, cost, l;int sum[100500][8];int dp[100500][8];int main(){	while(cin >> m >> n >> cost >> l)	{		int x;		for(int i = 1; i <= n; i++)		{			sum[0][i] = 0;			for(int j = 1; j <= m; j++)			{				scanf("%d", &x);				sum[j][i] = sum[j - 1][i] + x;			}		}		deque<int >q[8][8];		for(int i = 0; i <= m; i++)			for(int j = 0; j <= n; j++)				dp[i][j] = INF;		for(int j = 0; j <= n; j++)			dp[0][j] = 0;		/*for(int i = 1; i <= n; i++)			for(int k = 1; k <= n; k++)				q[i][k].push_back(0);*/		///////////////////////		for(int i = 0; i <= m; i++)		{			for(int j = 1; j <= n; j++)//删除头不符合条件的				for(int x = 1; x <= n; x++)//from				{					if(j == x)						continue;					while(!q[j][x].empty() 						&& i - l > q[j][x].front())						q[j][x].pop_front();				}			for(int j = 1; j <= n; j++)//单独考虑j				for(int x = 1; x <= n; x++)//from 从什么方向转移				{					if(j == x)						continue;					int v = 0;					if(!q[j][x].empty())						v = q[j][x].front();					dp[i][j] = min(dp[v][x] - sum[v][j] + sum[i][j] + cost, dp[i][j]);				}			for(int j = 1; j <= n; j++)//删除尾不单调（不最优的）				for(int x = 1; x <= n; x++)//from 				{					if(j == x)						continue;					while(!q[j][x].empty() 						&&  dp[i][x] - sum[i][j] <= 						dp[q[j][x].back()][x] - sum[q[j][x].back()][j])						q[j][x].pop_back();					q[j][x].push_back(i);				}		}		int ans = INF;		for(int i = 1; i <= n; i++)			ans = min(ans, dp[m][i]);		printf("%d\n", ans - cost);	}    return 0;}

vijos 1243 生产产品 DP + 单调队列优化