题解 P6246 【[IOI2000] 邮局 加强版】

皎月半洒花

2020-04-01 08:00:50

Solution

出了题没多少人做,还不小心卡了神 `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 ; } ``` #