洛谷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;
}