洛谷P4983 忘情题解

题意：

“为什么要离开我！”

“因为你没玩儿转！”

“我玩儿转了！”

“那好，你现在就给我维护这么一个式子！”

“为什么要出这么毒瘤的东西。”

“为了恶心你。”

“......”

\(……………………………\)

你的 \(npy\) 为了恶心你，特地请了四位大神和一个辣鸡！

\(\rm hdxrie\) 说：“我们得求和。”于是有了 \(\sum\limits_{i=1}^{n}x_i\) 。

\(\rm Imagine\) 说：“我们得有平均数。”于是有了 \(\bar x\) 。

\(\rm TimeTraveller\) 说：“我们得有加减乘除。”于是有了一些恶心的组合。

\(\rm Althen·Way·Satan\) 说：“我们还得有平方。”于是我们将它平方。

最垃圾的 \(\rm ZredXNy\) 说：“那我帮你们整合一下。”

于是，我们得到了这么一个式子 \(:\)

\[ \frac{\left((\sum\limits_{i=1}^{n}x_i×\bar x)+\bar x\right)^2}{\bar x^2} \]

我们定义一段序列的值为这个，其中 \(n\)为此序列的元素个数。

我们给定一段长度为 \(n\) 的序列,现在要求将它分成 \(m\) 段，要求每一段的值的总和最小，求出这个最小值。

对于 \(100 \%\) 的数据，\(m≤n≤100000\)，\(1≤x_i≤1000\)。

柿子化简懒得讲了，太简单了

最后化简出来每一段的花费就是 \[ (S_r-S_{l-1}+1)^2 \] 其中 \(S_k = \sum_{i=1}^{k}x_i\)

设 \(f_{i,k}\) 表示只考虑前 \(i\) 个物品分成 \(k\) 段的最小花费

显然可以wqs二分去掉 \(k\) 维（证明略） \[ f_i = \min_{j < i}\left\{f_j+(S_i-S_{j}+1)^2\right\}+d \] 令 \(a_i =S_i+1,b_j=S_j\) ，则 \[ \begin{aligned} f_i &= \min_{j < i}\left\{f_j+(a_i-b_j)^2\right\}+d \\&=\min_{j < i}\left\{f_j+a_i^2-2a_ib_j+b_j^2\right\}+d \end{aligned} \] 移项得 \[ f_i-a_i^2=\min_{j < i}\left\{f_j-2a_ib_j+b_j^2\right\}+d \] 设 \[ \begin{aligned} k_i &= 2a_i \\x_j &= b_j \\y_j &= f_j+b_j^2 \\b_i &= f_i-a_i^2 \end{aligned} \] 斜率优化 \(O(n\log 10^{16})\)

我的写法是二分的那条直线相等时优先选分的段最多的（所谓尽可能多选）

也就是斜率相等时，优先切最右边的点，显然这个点分的段更多一些

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
int pf(int x){return x*x;}
int n,m,st,en,sum[N],f[N],g[N],q[N];
int a(int i){return sum[i]+1;}
int b(int i){return sum[i];}
int X(int i){return b(i);}
int Y(int i){return f[i]+b(i)*b(i);}

double slope(int a,int b){return ((double)Y(b)-Y(a))/(X(b)-X(a));}
int ck(int d)
{
    f[0]=0; g[0]=0; q[st=en=1]=0;
    for(int i=1; i<=n; i++)
    {
        while(st<en&&slope(q[st],q[st+1])<=2.0*a(i))++st;
        f[i]=f[q[st]] + pf(a(i)-b(q[st]))+d;
        g[i]=g[q[st]]+1;
        while(st<en&&slope(q[en-1],q[en])>=slope(q[en-1],i))--en;
        q[++en]=i;
    }
    return g[n]>=m;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        cin >> sum[i];
        sum[i]+=sum[i-1];
    }
    int l=-1e16,r=1e16;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(ck(mid))l=mid;
        else r=mid-1;
    }
    ck(l);
    cout << f[n]-m*l;
    return 0;
}

当然这里还有一份尽可能少选的写法

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
int pf(int x){return x*x;}
int n,m,st,en,sum[N],f[N],g[N],q[N];
int a(int i){return sum[i]+1;}
int b(int i){return sum[i];}
int X(int i){return b(i);}
int Y(int i){return f[i]+b(i)*b(i);}

double slope(int a,int b){return ((double)Y(b)-Y(a))/(X(b)-X(a));}
int ck(int d)
{
    memset(f,0x3f,sizeof(f));
    memset(g,0,sizeof(g));
    f[0]=0; q[st=en=1]=0;
    for(int i=1; i<=n; i++)
    {
        while(st<en&&slope(q[st],q[st+1])<2.0*a(i))++st;
        f[i]=f[q[st]] + pf(a(i)-b(q[st]))+d;
        g[i]=g[q[st]]+1;
        while(st<en&&slope(q[en-1],q[en])>slope(q[en-1],i))--en;
        q[++en]=i;
    }
    return g[n]<=m;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        cin >> sum[i];
        sum[i]+=sum[i-1];
    }
    int l=0,r=1e16;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(ck(mid))r=mid;
        else l=mid+1;
    }
    ck(l);
    cout << f[n]-m*l;
    return 0;
}