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

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;

}