题解 P6246 【[IOI2000] 邮局 加强版】
皎月半洒花
2020-04-01 08:00:50
出了题没多少人做,还不小心卡了神 `iostream` 的 `cdq`,这就很尴尬/kk
______
这个东西,考虑朴素的dp,就显然是 $f_{i,j}$ 记一下,然后放 $k\to i$ 的中点就好了。这样复杂度是 $n^2k$ 的。
然后编一下发现有决策单调性,就可以 $O(nk\log n)$ 其二分+单调栈,甚至直接用二维决策单调性做到 $O(nk)$ 了。
然而并不可以过233
考虑去优化一下上面那种解法,发现 $k$ 这个限制可以通过wqs二分给消掉,就变成了如果建一次邮局需要额外支付 $mid$ 的代价,但是不限制建的次数时的最短距离和。这个东西就变成了一个1D/1D的 $dp$ ,并且也具有决策单调性。这一部分就可以继续单调栈+二分做到 $n\log V\log n$ 。
不过写了写发现似乎二分的常数还是很小的,$n=5\times 10^5$ 也只需要谷 $2.7s$ 、uoj $2s$ 左右。
```cpp
int tp ;
ll res ;
ll f[N] ;
ll sum[N] ;
int lrg[N] ;
int cnt[N] ;
int stk[N] ;
int base[N] ;
int n, m, k ;
using IPT::qr;
using IPT::qra;
using IPT::qrs;
using IPT::qrdb;
using OPT::qw;
using OPT::qwa;
using OPT::qws;
il ll calc(int l, int r){
ll h = (l + r + 1) / 2 ;
ll ret = sum[r] - sum[h] ;
ll d1 = 1ll * (h - l) * base[h] ;
ll d2 = 1ll * (r - h) * base[h] ;
return ret - d2 + d1 - sum[h] + sum[l] ;
}
il ll trans(ll p, ll x){
return f[p] + calc(p, x) ;
}
bool check(ll x){
stk[tp = 0] = 0 ;
int h = 0 ; lrg[0] = 1 ;
for (int i = 1 ; i <= n ; ++ i){
while (h < tp && lrg[h] < i)
++ h ; if (lrg[h] > i) -- h ;
f[i] = trans(stk[h], i) + x, cnt[i] = cnt[stk[h]] + 1 ;
while (tp && trans(stk[tp], lrg[tp]) >= trans(i, lrg[tp]))
stk[tp] = 0, lrg[tp] = n + 1, -- tp ;
int l = lrg[tp], r = n, mid, ans = n + 1 ;
while (l <= r){
int mid = (l + r) >> 1 ;
if (trans(stk[tp], mid) >= trans(i, mid))
ans = mid, r = mid - 1 ; else l = mid + 1 ;
}
if (ans <= n) stk[++ tp] = i, lrg[tp] = ans ;
}
res = f[n] - x * m ; return (bool)(cnt[n] < m) ;
}
int main(){
qr(n) ; qr(m) ;
for (int i = 1 ; i <= n ; ++ i)
qr(base[i]), sum[i] = sum[i - 1] + (ll)base[i] ;
ll l = 0, r = 1e9, mid, ans ;
lrg[0] = 1 ; sum[n + 1] = sum[n] ;
while (l <= r){
mid = (l + r) >> 1 ;
if (check(mid)) r = mid - 1 ;
else ans = mid, l = mid + 1 ;
}
check(ans) ; qw(res) ; return 0 ;
}
```
#