洛谷P4983 忘情 题解报告

题目地址

题意：

把正整数序列分隔为m个区间，若单个区间的元素之和为X，则其贡献为\((X+1)^2\)。求所有区间的贡献之和的最小值。

分析：

wqs二分+斜率优化dp。

用单调队列发可以达到\(O(n)\)，但注意，为了保证偏序关系，（以我个人代码习惯）当dp[i]有多个转移方向时要尽量选区间数量少的。

当斜率相同时，我让cnt小点的挤兑掉大的点，但这方面多少有点玄学，需要在++l的while式子中，使用<=而不是<。

思路

wqs二分+斜率优化dp，复杂度为\(O(nlogn)\)。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5+5;

struct Dat{
    ll x,y;
    ll cnt;
} q[maxn];
ll dp[maxn];
ll ar[maxn];
int n,m;

int check(ll c)
{
    int l=1,r=1;
    ll s=0;
    //dp[j]+si2-2sisj+2si+sj2-2sj+1, x=sj, y=dp[j]+sj2-2sj, k=2si, b=dp[i]-si2-2si-1
    q[1]={0,0,0};
    for(int i=1;i<=n;++i)
    {
        s+=ar[i];
        ll k=2*s;
        while(l<r && q[l+1].y-q[l].y<=k*(q[l+1].x-q[l].x))
            ++l;
        dp[i]=q[l].y-k*q[l].x+s*s+2*s+1+c;
        ll x=s, y=dp[i]+s*s-2*s;
        while(l<r && (q[r].y-q[r-1].y)*(x-q[r].x)>(y-q[r].y)*(q[r].x-q[r-1].x))
            --r;
        while(l<r && (q[r].y-q[r-1].y)*(x-q[r].x)==(y-q[r].y)*(q[r].x-q[r-1].x) && q[r].cnt<=q[l].cnt+1)
            --r;
        q[++r]={x,y,q[l].cnt+1};
    }
    //cout<<c<<" "<<q[r].cnt<<" "<<dp[n]<<endl;
    return q[r].cnt;
}

int main()
{
    cin.tie(0)->sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>ar[i];
    ll l=-1e15, r=1e15;
    while(r-l!=1)
    {
        ll mid=(l+r)>>1;
        if(check(mid)<m)
            r=mid;
        else
            l=mid;
    }
    check(l);
    cout<<dp[n]-m*l;
}