2 条题解
-
0
来一发李超。
总之为了避免麻烦，我们先把序列
reverse一下。我们令 表示在 处放守卫塔的最小代价。那么有：
$$f_i=\min\{f_j+ a_i+\sum\limits_{k=j+1}^{i-1}k-j \} $$那么答案就是 。然后 是个等差数列，长度为 ，首、末项分别为 和 ，则该式值为 。
则原式等价于：
$$f_i=\min\{-j\times i + \dfrac {j^2+j}2+f_j\}+a_i+\dfrac {i^2-i}2 $$令 ，，则 内值为 时李超的最低交点。
注意题目有必须在 号点（
reverse后）建站的要求。#define int long long namespace XSC062 { using namespace fastIO; const int inf = 1e18; const int maxn = 1e6 + 5; const int maxm = 1e6 + 5; #define lt (p << 1) #define rt (lt | 1) struct __ { int k, b; }; struct _ { int l, r, u; }; int n, tot; __ seg[maxn]; _ t[maxm << 2]; int f[maxn], a[maxn]; int min(int x, int y) { return x < y ? x : y; } void swap(int &x, int &y) { x ^= y ^= x ^= y; return; } void bld(int p, int l, int r) { t[p].l = l, t[p].r = r, t[p].u = 0; if (l == r) return; int mid = (l + r) >> 1; bld(lt, l, mid), bld(rt, mid + 1, r); return; } int getv(int id, int x) { if (!id) return inf; return x * seg[id].k + seg[id].b; } void upd(int p, int id) { if (!t[p].u) { t[p].u = id; return; } int mid = (t[p].l + t[p].r) >> 1; int v1 = getv(t[p].u, mid), v2 = getv(id, mid); if (v2 < v1) swap(t[p].u, id); v1 = getv(t[p].u, t[p].l); v2 = getv(id, t[p].l); if (v2 < v1) upd(lt, id); v1 = getv(t[p].u, t[p].r); v2 = getv(id, t[p].r); if (v2 < v1) upd(rt, id); return; } void add(int p, int l, int r, int id) { if (l <= t[p].l && t[p].r <= r) { upd(p, id); return; } int mid = (t[p].l + t[p].r) >> 1; if (l <= mid) add(lt, l, r, id); if (r > mid) add(rt, l, r, id); return; } int ask(int p, int x) { int res = inf; if (t[p].u) res = getv(t[p].u, x); if (t[p].l == t[p].r) return res; int mid = (t[p].l + t[p].r) >> 1; if (x <= mid) res = min(res, ask(lt, x)); else res = min(res, ask(rt, x)); return res; } int fun(int x) { return x * (x - 1) / 2; } int main() { read(n); bld(1, 1, n); for (int i = 1; i <= n; ++i) read(a[n - i + 1]); for (int i = 1; i <= n + 1; ++i) { if (i != 1) f[i] = ask(1, i) + a[i] + fun(i); else f[i] = a[i]; seg[++tot].k = -i; seg[tot].b = fun(i + 1) + f[i]; add(1, 1, n, tot); } print(f[n + 1], '\n'); return 0; } } // namespace XSC062 #undef int -
0
The_Shadow_Dragon
LV 7
@ 2023-7-21 15:17:40
令 , 为处理到第 个位置放置守卫塔的最小花费。
观察题意，容易得到在 时，有
$f_{i}= min\left \{ f_{j}+\sum\limits_{k=j+1}^{i-1} (i-k)+a_{i} \right \}$ ①
$f_{i}= min\left \{ f_{j}+\sum\limits_{k=j+1}^{i-1} (i-k) \right \} +a_{i}$ ②
$f_{i}= min\left \{ f_{j}+\sum\limits_{k=j+1}^{i-1}i-\sum\limits_{k=j+1}^{i-1}k \right \} +a_{i}$ ③
$f_{i}= min\left \{ f_{j}+(i-j-1)*i-\sum\limits_{k=j+1}^{i-1}k \right \} +a_{i}$ ④
$f_{i}= min\left \{ f_{j}+(i-j-1)*i-(S_{i-1}-S_{j} ) \right \} +a_{i}$ ⑤
此时若存在 ，且 比 更优时，则 $f_{j}+(i-j-1)*i-(S_{i-1}-S_{j} )<f_{k}+(i-k-1)*i-(S_{i-1}-S_{k} )$ ⑥ ，化简得 ⑦。
接着维护一个单调队列，复杂度
#include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' ll a[1000001],sum[1000001],f[1000001],q[1000001]; double work(ll x,ll y)//注意精度问题 { return 1.0*(f[y]-f[x]+sum[y]-sum[x])/(y-x); } int main() { ll n,i,l=0,r=0; cin>>n; for(i=1;i<=n;i++) { cin>>a[i]; sum[i]=sum[i-1]+i; } for(i=1;i<=n;i++) { while(l<r&&work(q[l],q[l+1])<i) { l++; } f[i]=f[q[l]]+(i-q[l]-1)*i-(sum[i-1]-sum[q[l]])+a[i];//直接套公式⑤ while(l<r&&work(q[r-1],q[r])>work(q[r],i)) { r--; } r++; q[r]=i; } cout<<f[n]; return 0; }写在最后：十年OI一场空，不开long long见祖宗。
- 1