在数轴上从\(0\)到\(n\)有\(n+1\)个点, 其中\(0\text{到}n-1\)这\(n\)个位置分别有公交车, 只能向数轴正方向移动, 每个点的公交车有两个属性\(c_i\)和\(v_i\), 分别表示隔几个点停一次(一站要经过几个点)和坐一站的花费, 求从\(0\)到每个点的最小花费, 无法到达者输出\(-1\).
\(n<=10^6, maxc<=10.\)
简单思考得到一个dp:设\(f_i\)是\(i\)点的最小花费, 转移显然.
思考如何优化转移:设当前已经求完答案的点为\(i\), 那么这个点对后面的点的影响可以看做一个一次函数(直线), 斜率为\(\frac{v_i}{c_i}\), 且有一个点\((i, f[i])\), 凭此即可确定函数解析式.
然而有一个问题:不是每一个点都能用这条直线来更新答案的.
怎样的点能被这条直线更新呢? 也就是说这条直线只有在公交车停的站才有贡献嘛! 所以满足条件的点的集合是
即
也就是只要\(j\operatorname{mod}c_i = i\operatorname{mod}c_i\) 即可被转移.
看数据范围:\(maxc<=10\)! 由于一共最多只有\(10\)种\(c\), 且\(i\operatorname{mod}c_i\)的取值最多不超过\(c_i\)种, 于是总共最多只有\(\sum_1^{10}i\)种情况, 即\(55\)种情况.
所以... 按照\(55\)种情况分类的话...
我们只用开\(55\)棵李超树就好了!!!
开这么多棵树空间复杂度怎么办呢? 容易想到动态开点. 由于一共只有\(n\)条直线, 所以只会有\(n\)个树节点.
对于每一个\(j\), 在李超树上枚举每一种\(c\), 设枚举的值为\(p\), 查询\((p, j \operatorname{mod} p)\)对应的李超树. 求完答案后丢进李超树即可.
由于李超树查询的复杂度是\(O(\log{n})\), 插入的复杂度是\(O(\log^2{n})\), 一个点要做\(maxc\)次查询和\(1\)次插入, 所以总时间复杂度为\(O(n(maxc\cdot\log{n}+\log^2{n}))\)
虽然\(n<=10^6\), 但是由于 数据可能是随机的 做人要有信仰 节点数比较少根本跑不满,并且时限2s, 所以简 单 的常数优化以后就能过了.
这种题, 思路很自然, 但是时间复杂度比较清奇, 所以考场没敢写. 实际上就算被卡了也会有\(80pts\), 所以以后要大胆写算法, 大胆开数据结构, 有时间会学习优秀的单调栈做法咕咕咕咕...
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 1000010
#define db double
#define ll long long
#pragma GCC optimize(2)
#define INF 0x3f3f3f3f3f3f3f3fll
#define init(a, b) memset(a, b, sizeof(a))
#define fo(i, a, b) for(int i = (a); i <= (b); ++i)
#define fd(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
inline int read()
{
int x = 0; char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘) ch = getchar();
while(ch >= ‘0‘ && ch <= ‘9‘) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
return x;
}
int n, c[N], v[N];
ll f[N];
struct Line
{
db k, b;
Line(){k = 0, b = INF;}
Line(db _k, db x, db y){k = _k; b = y - k * x;}
inline db y(db x){return k * x + b;}
};
namespace Seg
{
int cnt, to[11][11], rt[60], ls[N], rs[N];
Line tr[N];
inline void build(int k, int i){static int tot = 0; !rt[to[k][i]] && (rt[to[k][i] = ++tot] = ++cnt);}
void insert(int t, int l, int r, Line p)
{
int mid = (l + r) >> 1;
db lx = tr[t].y(l) - p.y(l), mx = tr[t].y(mid) - p.y(mid), rx = tr[t].y(r) - p.y(r);
if(lx >= 0 && rx >= 0) tr[t] = p;
else if(lx < 0 && rx >= 0)
{
if(mx >= 0) !ls[t] && (ls[t] = ++cnt), insert(ls[t], l, mid, tr[t]), tr[t] = p;
else !rs[t] && (rs[t] = ++cnt), insert(rs[t], mid + 1, r, p);
}
else if(lx >= 0 && rx < 0)
{
if(mx >= 0) !rs[t] && (rs[t] = ++cnt), insert(rs[t], mid + 1, r, tr[t]), tr[t] = p;
else !ls[t] && (ls[t] = ++cnt), insert(ls[t], l, mid, p);
}
}
inline void insert(int k, int i, Line p){build(k, i); insert(rt[to[k][i]], 1, n, p);}
db query(int t, int l, int r, int x)
{
db ret = tr[t].y(x);
int mid = (l + r) >> 1;
if(x <= mid){if(ls[t]) ret = min(ret, query(ls[t], l, mid, x));}
else if(rs[t]) ret = min(ret, query(rs[t], mid + 1, r, x));
return ret;
}
inline db query(int k, int i, int x){return rt[to[k][i]] ? query(rt[to[k][i]], 1, n, x) : INF;}
}
int main()
{
freopen("bus.in", "r", stdin);
freopen("bus.out", "w", stdout);
n = read(), c[0] = read();
fo(i, 1, n) c[i - 1] = read(), v[i - 1] = read();
Seg::insert(c[0], 0, Line(1.0 * v[0] / c[0], 0.0, 0.0));
fo(i, 1, n)
{
f[i] = INF;
fo(j, 1, 10)
f[i] = min(f[i], (ll)(Seg::query(j, i % j, i) + 0.5));
printf("%lld ", f[i] == INF ? -1 : f[i]);
f[i] != INF && i < n && (Seg::insert(c[i], i % c[i], Line(1.0 * v[i] / c[i], i, f[i])), 1);
}
return 0;
}
原文：https://www.cnblogs.com/Martin-MHT/p/14291079.html