自动搬运

查看原文

来自洛谷，原作者为

	_zuoqingyuan 蒟蒻

搬运于2025-08-24 23:03:00，当前版本为作者最后更新于2024-11-17 12:36:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

“你只能做一个操作——减少序列中的一些数字”。

因为没看见这句话瞪这题瞪了两周。

前置：斜率优化 dp，模板题。

思路分析

怎么没有单调队列题解？

设 $dp_i$ 表示将 $a_{1\sim i}$ 修改为 K-Anonymous 序列的最小花费。

对于 $i<k$，显然不可能修改为合法序列。

对于 $i\ge k$，我们可以枚举 $j$，将 $a_{j+1\sim i}$ 修改为一段相同的数字，并将这段的花费累加到 $dp_j$ 上用来更新 $dp_i$。其中 $j\le i-k$。

因为我们只能减小某个数字，而序列单调不下降，所以我们只能把 $a_{j+1\sim i}$ 都修改为 $a_{j+1}$。

记 $S_i=\sum\limits_{j=1}^ia_j$，则：

$$dp_i=\begin{cases}\infty&i<k\\dp_j+(S_i-S_j)-(i-j)a_{j+1}&i\ge k\end{cases} $$

我们主要对后一种情况进行讨论，$k\gets k-1$。

$$dp_i=\min_{0\le j< i-k}\{dp_j+S_i-S_j-(i-j)a_{j+1}\} $$

把式子拆开，去掉 $\min$。

$$dp_i=dp_j+S_i-S_j-ia_{j+1}+ja_{j+1}$$

我们发现式子中只有一项同时包含 $i,j$。显然可以斜率优化，移项得。

$$dp_j-S_j+ja_{j+1}=ia_{j+1}+dp_i-S_i$$

令

$$y=dp_j-S_j+ja_{j+1}$$ $$k=i$$ $$x=a_{j+1}$$ $$b=dp_i-S_i$$

则式子可以化为 $y=kx+b$ 的形式。因为 $a$ 单调不下降，所以 $k,x$ 均具有单调性，可以直接用单调队列，时间复杂度 $O(n)$。

$\text{Code}：$

#include <iostream>
#include <cstring>
#include <cstdio>
#define int long long//防止爆 int
using namespace std;
const int N=5e5+10;
int n,k,a[N],s[N],l,r,q[N],dp[N];
inline int X(int x){return a[x+1];}
inline int Y(int x){return dp[x]-s[x]+x*a[x+1];}
void work(){
    scanf("%lld %lld",&n,&k);k--;
    for(int i=1;i<=n;i++)scanf("%lld",a+i),s[i]=a[i]+s[i-1];
    q[l=r=1]=0;dp[0]=0;//初始化
    for(int i=1,j;i<=n;i++){
        if(i<=k){dp[i]=0x3f3f3f3f;continue;}
        while(l<r&&(Y(q[l+1])-Y(q[l]))<=i*(X(q[l+1])-X(q[l])))l++;//防止精度误差
        dp[i]=dp[j=q[l]]+s[i]-s[j]-(i-j)*a[j+1];
        while(l<r&&(Y(q[r])-Y(q[r-1]))*(X(i-k)-X(q[r]))>=(Y(i-k)-Y(q[r]))*(X(q[r])-X(q[r-1])))r--;//防止精度误差
        q[++r]=i-k;//决策入队
    }
    printf("%lld\n",dp[n]);
    return;
}
void clear(){//清空
    memset(q,0,sizeof(q));
    memset(dp,0,sizeof(dp));
    l=r=0;
    return;
}
signed main(){
    int T=0;
    cin>>T;
    while(T--){
        work();
        clear();
    }
    return 0;
}

如有错误，请指出。