Codeforces 721E Road to Home

题意

输入第一行有4个数，分别为\(L,n,p,t\),分别表示总长度为\(L\)的路，中间有\(n\)个互不相交的区间，现在要用长度为\(p\)的小木棒从左往右铺路（木棒不能被折断，也不能有重叠，且所有的木棒必须在区间内），你可以连续铺路，但是一旦你主动或被迫中断铺路（比如区间内剩下的长度不足以放下一根木棍）那么下一根开铺的木棍最少也要在\(t\)距离之后。问最多能铺多少根木棍。接下来的\(n\)行表示从左到右的\(n\)个区间。

想法

首先当然是想暴力的算法...dp？

\(f_i\)表示铺完前\(i\)个区间最多能铺的木棍数，\(g_i\)表示前\(i\)个区间铺了最多的木棍时最右端的木棍的右端最左可以取到的地方。

暴力转移？

\[f_i = \max_{ g_j+t<=r_i} \{ f_j + \lfloor \frac{r_i - \max \{l_i, g_j + t\}}{p} \rfloor \}
\]

\[g_i = \max \{ l_i, g_j + t\} + \lfloor \frac{r_i - \max \{l_i, g_j + t\}}{p} \rfloor * p
\]

之后由观察/打表可以发现，\(g_i\)是不减的，决策也是不减的，那么这就可以用到“单调队列”。

每次转移时不断从队头取出元素，如果有更优的决策那么就从队头pop出去，更新了就把得到的状态加入到队尾。

注意这里的更优不仅要考虑\(f_i\)的更大，在\(f_i\)相同时也要考虑\(g_i\)的更小。

Code

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ll long long

#define db double

#define N 100010

#define max(a, b) ((a) > (b) ? (a) : (b))

#define min(a, b) ((a) < (b) ? (a) : (b))

#define swap(T, a, b) ({T ttt = a; a = b; b = ttt;})

#define x f[q[tl]]

#define y g[q[tl]]

int L, n, p, t, f[N], g[N], l[N], r[N], Ans = 0, q[N], tl, tr, tA, tB;

bool Q;

int main()

{

	scanf("%d%d%d%d", &L, &n, &p, &t);

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

		scanf("%d%d", &l[i], &r[i]);

	f[0] = 0; g[0] = -t; q[tl = tr = 0] = 0;

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

	{

		tA = tB = 0; Q = false;

		while (tl <= tr && y + t <= r[i] && x + (r[i] - max(l[i], y + t)) / p > tA)

		{

			tA = x + (r[i] - max(l[i], y + t)) / p;

			tl++; Q = true;

		}

		if (Q) tl--;

		else tA = x + (r[i] - max(l[i], y + t)) / p;

		tB = max(l[i], y + t) + (r[i] - max(l[i], y + t)) / p * p;

		Q = false;

		while (tl <= tr && y + t <= r[i] && x + (r[i] - max(l[i], y + t)) / p == tA)

		{

			tB = min(tB, max(l[i], y + t) + (r[i] - max(l[i], y + t)) / p * p);

			tl++; Q = true;

		}

		if (Q) tl--;

		f[i] = tA; g[i] = tB;

		if (f[i] > Ans) { Ans = f[i]; q[++tr] = i; }

	}

	printf("%d\n", Ans);

	return 0;

}

巴特西

Codeforces 721E Road to Home

题意

想法

Code

最新文章

热门文章