【Codeforces Round #466】E. Cashback DP+ST表

题意

给定$n$个数，将其划分成若干个连续的子序列，求最小价值，数组价值定义为，数组和减去$\lfloor \frac{k}{c} \rfloor$,$k$为数组长度，$c$为给定数

---

可以列得朴素方程$f_i=\min_{j \le i} {f_j+w(j+1,i)}$，复杂度$O(n^2)$

考虑划分的区间长度$k$，若$k=c$，那么只需要去掉区间的最小值，若$k$是$c$的整数倍，那么需要去掉$k/c$个最小值，那么把$k$分成$k/c$个长度为$c$的段，删除的最小值为每个段的最小值之和一定不小于长度为$k$的段的$k/c$个最小值的和，所以最优的分段一定是分成若干个长度为$c$的段

在考虑$k$不被整除的情况，若$k=c+p,p < k$，那么这一段也只会删掉一个最小值，随着$p$的增大，最小值单调不增，所以不会更优。若$k<c$，那么将不会删除值，也就是代价不会转移，可以将其看成分成$k$个$1$

所以可以将方程化简为$f_i=\min {f_{i-1},f_{i-c}+u(j+1,i) }$ ,$u(i,j)$为$[i,j]$的区间和减去区间最小值，可以利用st表预处理得到

时间复杂度$O(n\log n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int n, c, a[100005], st[100005][35];

LL dp[100005], sum;

int min_(int l, int r) {

    int x = (int)(log(double(r - l + 1)) / log(2.0));

    return min(st[l][x], st[r - (1 << x) + 1][x]);

}

int main() {

    scanf("%d%d", &n, &c);

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

        scanf("%d", &a[i]); st[i][0] = a[i]; sum += a[i];

    }

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

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

            st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);

        }

    }

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

        dp[i] = max(dp[i - 1], dp[i - c] + min_(i - c + 1, i));

    }

    cout << sum - dp[n] << endl;

    return 0;

}