洛谷 4983 忘情

化式子先。 (¯xn∑i=1xi+¯x)2¯x2=¯x2(n∑i=1xi)2+2¯x2n∑i=1xi+¯x2¯x2=(n∑i=1xi)2+2n∑i=1xi+1=(n∑i=1xi+1)2

朴素方程有 Fi,k=min0≤j<i(Fj,k−1+(sumi−sumj+1)2)。
其中 sumi=i∑j=1xj。

首先不考虑段数的限制，方程即 fi=min0≤j<i(fj+(sumi−sumj+1)2)。
假设决策 0≤k<j<i 使得 j 优于 k，即 fj+(sumi−sumj+1)2<fk+(sumi−sumk+1)2fj−2sumi(sumj−1)+(sumj−1)2<fk−2sumi(sumk−1)+(sumk−1)2(fj+(sumj−1)2)−(fk+(sumk−1)2)<2sumi(sumj−sumk)(fj+(sumj−1)2)−(fk+(sumk−1)2)sumj−sumk<2sumi

注意这个地方如果要使用 WQS 二分的话不能包含斜率等于 2sumi 的情况，否则会错（可能没有单调性）。

然后来考虑一下段数的限制，如果直接 O(nm) DP 肯定不行，但是我们发现如果没有这个段数就可以 O(n) 过去。
所以我们就有了 WQS 二分。
主要思想是，如果转移方程是 fi=min0≤j<i(fj+(sumi−sumj+1)2+C)，那么 C 越大影响就越大，段数就越少；反之亦然。
所以我们就二分这个 C，找到第一个使得段数 ≤m 的整数 C。

代码：

#include <cstdio>
using namespace std;
const int N = 1e5;
int n,m;
int g[N + 5];
long long sum[N + 5],f[N + 5];
int q[N + 5],head,tail;
long long l,r,mid,ans;
inline double slope(int x,int y)
{
    return (double)(f[x] + (sum[x] - 1) * (sum[x] - 1) - f[y] - (sum[y] - 1) * (sum[y] - 1)) / (sum[x] - sum[y]);
}
int check()
{
    q[head = tail = 1] = 0;
    for(register int i = 1;i <= n;++i)
    {
        for(;head < tail && slope(q[head],q[head + 1]) < 2 * sum[i];++head);
        f[i] = f[q[head]] + (sum[i] - sum[q[head]] + 1) * (sum[i] - sum[q[head]] + 1) + mid,g[i] = g[q[head]] + 1;
        for(;head < tail && slope(q[tail - 1],q[tail]) > slope(q[tail],i);--tail);
        q[++tail] = i;
    }
    return g[n] <= m;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%lld",sum + i),sum[i] += sum[i - 1];
    l = 0,r = 0x3f3f3f3f3f3f3f3f;
    while(l <= r)
    {
        mid = l + r >> 1;
        if(check())
            r = mid - 1,ans = mid;
        else
            l = mid + 1;
    }
    mid = ans,check();
    printf("%lld\n",f[n] - ans * m);
}