题目大意

• 给定长度为 $n$ 的序列 $a$ 和一个整数 $c$。

• 将其分成若干段，若该段长度为 $k$，就删除该段中前 $\left\lfloor\dfrac kc\right\rfloor$ 小的数。

• 求剩余数总和最小值。

• $1\leq n,\ c\leq 10^5$，$1\leq a_i\leq 10^9$

解题思路

对于一段长度为 $k$ 的数：

• 若 $\left\lfloor\dfrac kc\right\rfloor=0$ 即 $k<c$，则该段不会被删除数，将该段任意分割也是如此。

• 若 $k=ct+p$（$t,\ p$ 为整数且 $t\geq 1,\ p<c$），则将这一段分成 $t$ 段有 $c$ 个数的段和一段有 $p$ 个数的段后，有 $c$ 个数的段各删除一个最小值，共删除 $t$ 个数。而原先删除的是该段中最小的 $t$ 个数，必定不比分割后删除的数总和。

接下来还有若干长度 $<c$ 的段，其中不会删除数，为了方便，不妨将它们全部拆成长度为 $1$ 的段。

此时序列被分为若干长度为 $1$ 的段和若干长度为 $c$ 的段，故最优解必定由长度为 $1$ 或 $c$ 的段组成。

考虑动态规划。设 $dp_i$ 表示前 $i$ 个数分割成长度为 $1$ 或 $c$ 的段，删除数总和的最大值。显然 $dp_0=0$。

计算 $dp_i$ 时，对第 $i$ 个数所在段的长度分类，易得

$$dp_i= \begin{cases} dp_{i-1}, &\text{if }n\text{ is even} \\ \min\left\{dp_{i-1},dp_{i-c}+\min\limits_{j=i-c+1}^{i}a_j\right\},&\text{if }n\text{ is odd} \end{cases}. $$

而答案要求的是剩下数的总和，即 $\sum\limits_{i=1}^na_i-dp_n$。

时间复杂度 $\Theta(n\log n)$（ST 表预处理或线段树查询 $n$ 次产生的时间复杂度）。

AC 代码

#include<bits/stdc++.h>
using namespace std;

int n,c,a[100001];
int minn[100001][18];
long long sum,dp[100001];

inline int Min(int l,int r){
    int t=log2(r-l+1);
    return min(minn[l][t],minn[r-(1<<t)+1][t]);
}

int main(){
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i),minn[i][0]=a[i],sum+=a[i];
    for(int i=1,t=log2(n);i<=t;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            minn[j][i]=min(minn[j][i-1],minn[j+(1<<i-1)][i-1]);
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1];
        if(i>=c)dp[i]=max(dp[i],dp[i-c]+Min(i-c+1,i));
    }
    printf("%lld\n",sum-dp[n]);
    return 0;
}