Description

题库链接

给你两个整数 \(n,c\) ，以及一个数列 \(A\) ，让你将序列分为许多段。对于每一段，他的价值为序列内除了最小的 \(\left\lfloor\frac{lenth}{c}\right\rfloor\) 个元素以外的其他所有元素和， \(lenth\) 为该段的长度。最小化这个价值和。

\(1\leq n,c\leq 100000,1\leq A_i\leq 10^9\)

Solution

一个由贪心得出的结论是整个序列只要分为若干个长度为 \(c\) 的段和若干个长度为 \(1\) 的段即可。

既然要最小化价值，相当于删去的数要尽可能大。

首先分一段长度为 \(c+x,x<c\) 的段，不如分为一段为 \(c\) ， \(x\) 段长度为 \(1\) 。因为无论哪种分法都只能删去一个数，但第二种考虑的范围更广一些。

其次分一段长度为 \(2c\) 的段，不如分 \(2\) 段长度为 \(c\) 的段。假设 \(2c\) 段内的最小值和次小值的位置均在前半段内；若我用第二种方法分就一定能够更优。

由此，我们令 \(f_i\) 为转移到 \(i\) 这个位置时之前的最小价值和，转移的时候只要考虑长度分为 \(1\) 和 \(c\) 的情况。对于要删去最小值，用 \(st\) 表来实现查找最值就可以了。

复杂度为 \(O(n~log_2n)\) ，瓶颈在预处理 \(st\) 表，转移是 \(O(n)\) 的。

Code

//It is made by Awson on 2018.2.25

#include <bits/stdc++.h>

#define LL long long

#define dob complex<double>

#define Abs(a) ((a) < 0 ? (-(a)) : (a))

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

#define writeln(x) (write(x), putchar('\n'))

#define lowbit(x) ((x)&(-(x)))

using namespace std;

const int N = 1e5;

void read(int &x) {

    char ch; bool flag = 0;

    for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());

    for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());

    x *= 1-2*flag;

}

void print(LL x) {if (x > 9) print(x/10); putchar(x%10+48); }

void write(LL x) {if (x < 0) putchar('-'); print(Abs(x)); }

int n, c, a[N+5], st[N+5][20], lim, limc, bin[25];

LL f[N+5], sum[N+5];

int query(int l, int r) {return Min(st[l][limc], st[r-bin[limc]+1][limc]); }

void work() {

    read(n), read(c); lim = log(n)/log(2), limc = log(c)/log(2);

    bin[0] = 1; for (int i = 1; i <= 20; i++) bin[i] = bin[i-1]<<1;

    for (int i = 1; i <= n; i++) read(a[i]), st[i][0] = a[i];

    for (int i = 1; i <= n; i++) sum[i] = sum[i-1]+a[i];

    for (int t = 1; t <= lim; t++) for (int i = 1; i+bin[t]-1 <= n; i++) st[i][t] = Min(st[i][t-1], st[i+bin[t-1]][t-1]);

    for (int i = 1; i <= n; i++) {

    f[i] = f[i-1]+a[i];

    if (i >= c) f[i] = Min(f[i-c]+sum[i]-sum[i-c]-query(i-c+1, i), f[i]);

    }

    writeln(f[n]);

}

int main() {

    work(); return 0;

}