题解 P4767 【[IOI2000]邮局】

· · 题解

读完题我们会发现这个题可以用wqs二分来优化dp。

我们会看出两个性质

设g(i)表示放i个邮局的最小代价，则有

第一个非常的显然。

第二个结论我们考虑每次放邮局的过程，放入当前邮局会使一段区间内的村庄减小代价，而我们要找到减小代价最多的这一个区间，而我们上一次放入使得这个区间变多了，如果说上一次放的时候有一个区间比我这次放的区间优，那么上一次我就会放这个区间，所以说这次减少的代价一定比上一次少。

定义f(i)表示在放邮局会额外产生k的代价下，放i个邮局产生的最小代价。

于是我们二分斜率k，我们要找到一个最小的f(i)，然而这个东西并不好求。

那么我们设h(i)表示前i个村庄可以放若干个邮局，可以产生的最小代价，然后我们记pre(i)表示前i个村庄放pre(i)个邮局最优，当h(i)从h(j),j<i转移过来时，pre(i)=pre(j)+1。

那么可以轻松地写出转移方程

h(i)=min_{j=0}^{i-1}h(j)+dist(j+1,i)+k

其中dist(l,r)表示往l,r中放一个村庄的最小代价，这个东西非常好求，只需要往这个区间的中间放邮局就可以了。

这样子直接转移是O(n^2)的，所以我们要考虑优化。

首先先证明dist满足四边形不等式，也就是证明对于任意a<b，都有dist(a,b)+dist(a+1,b+1)\le dist(a+1,c)+dist(a,c+1)。

证明：

设s_i=\sum_{j=1}^ia_j那么

dist(l,r)=s_r-s_{mid}-a_{mid}\times(r - mid)+a_{mid}\times(mid - l)-(s_{mid - 1}-s_{l - 1}),mid=\frac{l+r}{2}

然后注意到dist(a+1,b+1)和dist(a,b+1)取的mid相同，记作mid_1，那么dist(a,b+1)-dist(a+1,b+1)=s_{mid_1}-s_a。

记dist(a,b)和dist(a+1,b)的mid为mid_2，可得dist(a,b)-dist(a+1,b)=s_{mid_2}-s_a

于是移项得

dist(a,b)+dist(a+1,b+1)-dist(a+1,c)-dist(a,c+1)=s_{mid_2}-s_a-(s_mid_2-s_a)=s_{mid_2}-s_{mid_1}

而mid_2<mid_1，所以s_{mid_2}-s_{mid_1}\le0，所以原式成立

证毕

然后我们关注到一个性质：一个点作为最优点转移到的点一定构成一个区间，也就是对于一个i，不存在a<b<c，i是最优点转移到a和c，但不是最优解转移到b。

如何证明这个结论，我们考虑反证法。（后面的作为最优解转移直接写作转移）

证明：

假设存在i,j,a,b,c满足i\ne j,a<b<c且i只能转移到a,c，不能转移到b，j能转移到b。

那么可得几个不等式

h(i)+dist(i+1,a)+k\le h(j)+dist(j+1,a)+k h(i)+dist(i+1,b)+k> h(j)+dist(j+1,b)+k h(i)+dist(i+1,c)+k\le h(j)+dist(j+1,c)+k

整理得

dist(j+1,a)+dist(i+1,b)>dist(j+1,b)+dist(i+1,a) dist(j+1,c)+dist(i+1,b)>dist(j+1,b)+dist(i+1,c)

而由于dist满足四边形不等式，所以无法同时满足上述的两个式子，所以假设不成立。

证毕

然后我们可以用队列维护之前的决策点可以转移到哪个区间，到一个新的点的时候就二分找出这个点可以被哪个点转移，然后再二分找到这个点可以转移到的区间放进队列里。

这样复杂度是O(VlogVlog\sum a)。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define reg register
const int N = 3e3;
const int M = 300;
using namespace std;
struct que
{
    int p,l,r;
}q[N + 5];
int n,m,a[N + 5],s[N + 5],f[N + 5],pre[N + 5],ans;
inline int dist(int l,int r)
{
    int mid = l + r >> 1;
    return s[r] - s[mid] - a[mid] * (r - mid) + a[mid] * (mid - l) - (s[mid - 1] - s[l - 1]);
}
inline int check(int k)
{
    int R = 0;
    q[++R] = (que){0,1,n};
    for (reg int i = 1;i <= n;i++)
    {
        int l = 1,r = R,p,mid;
        while (l <= r)
        {
            mid = l + r >> 1;
            if (q[mid].l <= i)
                l = mid + 1,p = mid;
            else
                r = mid - 1;
        }
        f[i] = f[q[p].p] + dist(q[p].p + 1,i) + k;
        pre[i] = pre[q[p].p] + 1;
        p = 0;
        while (R && f[i] + dist(i + 1,q[R].l) + k <= f[q[R].p] + dist(q[R].p + 1,q[R].l) + k)
            p = q[R--].l;
        if (R && f[i] + dist(i + 1,n) + k <= f[q[R].p] + dist(q[R].p + 1,n) + k)
        {
            l = q[R].l,r = n;
            while (l <= r)
            {
                mid = l + r >> 1;
                if (f[i] + dist(i + 1,mid) + k <= f[q[R].p] + dist(q[R].p + 1,mid) + k)
                    r = mid - 1,p = mid;
                else
                    l = mid + 1;
                q[R].r = p - 1;
            }
        }
        if (p)
            q[++R] = (que){i,p,n};
    }
    return pre[n];
}
int main()
{
    scanf("%d%d",&n,&m);
    for (reg int i = 1;i <= n;i++)
        scanf("%d",&a[i]),s[i] = s[i - 1] + a[i];
    int l = 0,r = 3e7,mid;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (check(mid) >= m)
            l = mid + 1,ans = f[n] - m * mid;
        else
            r = mid - 1;
    }
    cout<<ans<<endl;
    return 0;
}