bzoj4368 IOI2015 boxes纪念品盒

题目链接：https://lydsy.com/JudgeOnline/problem.php?id=4368

数据范围：略。

题解：

如果在一个最优方案中，一个点$i$是这个人拿东西从左侧走过来的，我们就说这个点是蓝的。

如果是右侧的，就说这个点是红。

我们发现，并不存在三个可以不连续的点，满足红蓝红。

即，一定存在一个点$i$，满足$1\sim i$的点是蓝的，$i + 1\sim n$是红的。

接着我们维护一个$dp$状态：$f_i$，表示从$0$开始，把$1\sim i$都从左侧删掉并且回到原点的最小代价；$g_i$表示右侧的最小代价。

考虑$f$怎么转移？

显然，$f_i = min\{ f_j \} (i-j\le k)+a_i+min(a_i, L - a_i)$。

这个可以用线段树啊树状数组什么的优化。但是因为$n$是$10^7$，所以我们用单调队列即可。

代码：

#include <bits/stdc++.h>

#define setIO(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout) 

#define N 10000010 

using namespace std;

typedef long long ll;

char *p1, *p2, buf[100000];

#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

int rd() {

	int x = 0;

	char c = nc();

	while (c < 48) {

		c = nc();

	}

	while (c > 47) {

		x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();

	}

	return x;

}

int q[N], a[N];

ll dis[N], f[N], g[N];

int main() {

	// setIO("box");

	int n = rd(), k = rd(), L = rd();

	for (int i = 1; i <= n; i ++ ) {

		a[i] = rd();

		dis[i] = min(a[i], L - a[i]);

	}

	int head = 1, tail = 0;

	q[ ++ tail] = 0;

	for (int i = 1; i <= n; i ++ ) {

		f[i] = f[q[head]] + a[i] + dis[i];

		while (head <= tail && f[i] < f[q[tail]])

			tail -- ;

		while (head <= tail && i - q[head] >= k) {

			head ++ ;

		}

		q[ ++ tail] = i;

	}

	head = 1, tail = 0;

	q[ ++ tail] = n + 1;

	for (int i = n; i; i -- ) {

		g[i] = g[q[head]] + L - a[i] + dis[i];

		while (head <= tail && g[i] < g[q[tail]]) {

			tail -- ;

		}

		while (head <= tail && q[head] - i >= k) {

			head ++ ;

		}

		q[ ++ tail] = i;

	}

	// for (int i = 0; i <= n + 1; i ++ ) {

	// 	printf("%d : %lld %lld\n", i, f[i], g[i]);

	// }

	ll ans = 0x3f3f3f3f3f3f3f3fll;

	for (int i = 0; i <= n; i ++ ) {

		ans = min(ans, f[i] + g[i + 1]);

	}

	cout << ans << endl ;

}

巴特西

[bzoj4368][IOI2015]boxes纪念品盒_动态规划_单调队列_贪心

bzoj4368 IOI2015 boxes纪念品盒

最新文章

热门文章