题解：P10966 K-Anonymous Sequence

· · 题解

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

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

前置：斜率优化 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;
}

如有错误，请指出。