GMOJ S5415 【公交运输】

Description

一个长度为 $n$ 的数轴，第 $i$ 个位置有一辆车，它会在往后的每 $c_i$ 个位置停一次，两个停靠站之间的费用为 $v_i$。现在请你求出位置 $0$ 到位置 $1 ∼ n$ 的最短距离。

$$1 \leq n \leq 10^6, 1 \leq \max\{c_i\} \leq 10, 1 \leq v_i \leq 10^3$$

Solution

发现当两个在位置 $i$ 和 $j$ 的车停靠的位置相同，当且仅当 $c_i = c_j, i \mod c_i = j \mod c_j$。

于是所有的车可以被分为 $55$ 类。

考虑一下暴力 $O(n^2)$ 的 DP 怎么写，不难得出转移式：

$$f_i = \min_{c_j | (i - j)}\{f_j + \dfrac{i - j}{c_j} \times v_j\}$$

然后考虑斜率优化，转化一下式子：

$$f_i = \dfrac{i \times v_j}{c_j} + f_j - \dfrac{j}{c_j} \times v_j$$ $$f_i = v_j \times \dfrac{i}{c_j} + (f_j - \dfrac{j}{c_j} \times v_j)$$

令 $k = v_j, x = \dfrac{i}{c_j}, b = f_j - \dfrac{j}{c_j} \times v_j$，则 $f_i = kx + b$，然后就可以愉快地进行斜率优化了。

Code

#include <cstdio>
#include <cstring>
#define maxN 1000010
struct stack{ int k, b; } p[60][2010];
int size[60], val[maxN], c[maxN], f[maxN];
int min (int x, int y)
{
	return x < y ? x : y;
}
int change (int x, int y)
{
	return x * (x - 1) / 2 + (y + 1);
}
int calc (int k, int x, int b)
{
	return k * x + b;
}
int check (int k, int b, int kk, int bb)
{
	return (bb - b) / (k - kk);
}
int main ()
{
	int n = 0, maxC = 0;
	scanf("%d %d", &n, &maxC);
	for(int i = 0;i < n; i++)
	{
		scanf("%d %d", &c[i], &val[i]);
	}
	memset(f, 127 / 3, sizeof(f));
	const int inf = f[0];
	f[0] = 0;
	int x = c[0], y = 0;
	int z = change(x, y);
	p[z][++size[z]].k = val[0];
	for(int i = 1;i <= n; i++)
	{
		for(int j = 1;j <= maxC; j++)
		{
			int x = j, y = i % j;
			int z = change(x, y);
			int &N = size[z];
			if(!N)
			{
				continue;
			}
			if(N > 1 && calc(p[z][N].k, i / j, p[z][N].b) >= calc(p[z][N - 1].k, i / j, p[z][N - 1].b))
			{
				N--;
			}
			f[i] = min(f[i], calc(p[z][N].k, i / j, p[z][N].b));
		}
		if(f[i] == inf || i == n)
		{
			continue;
		}
		int x = c[i], y = i % c[i];
		int z = change(x, y);
		int &N = size[z];
		while(N && p[z][N].k >= val[i])
		{
			N--;
		}
		int k = val[i];
		int b = f[i] - (i / c[i]) * val[i];
		while(N > 1 && check(p[z][N - 1].k, p[z][N - 1].b, p[z][N].k, p[z][N].b) <= check(p[z][N].k, p[z][N].b, k, b))
		{
			N--;
		}
		N++;
		p[z][N].k = k, p[z][N].b = b;
	}
	for(int i = 1;i <= n; i++)
	{
		printf("%d ", f[i] == inf ? -1 : f[i]);
	}
	return 0;
}