题意是说将$n$个数字分段使得每段贡献之和最小，每段的贡献为区间和减去前$left lfloor frac{k}{c} ight floor$小的和。
仔细分析一下可以知道，减去$2$个可以分成减去$2$次$1$个，所以就可以设一个$dp:$$dp[i]$为$1-i$位的最小和.
$dp[i]=dp[i-1]+a[i]$，表示第$i$个单独分成一组。
$dp[i]=dp[i-m]+sum[i]-sum[i-m]-Q(i-m+1,i)$，表示第$i-c$到第$i$个分成一组，就要减去区间内的最小值。
所以ST表预处理一下
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e5 + 10; 5 ll dp[maxn], lg[maxn], Min[maxn][20], a[maxn], sum[maxn]; 6 ll Q(int l, int r) { 7 int k = lg[r - l + 1]; 8 return min(Min[l][k], Min[r - (1 << k) + 1][k]); 9 } 10 int main() { 11 int n, m; 12 scanf("%d%d", &n, &m); 13 for (int i = 1; i <= n; i++) 14 scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i]; 15 lg[0] = -1; 16 for (int i = 1; i <= n; i++) { 17 if ((i & (i - 1)) == 0) 18 lg[i] = lg[i - 1] + 1; 19 else 20 lg[i] = lg[i - 1]; 21 } 22 for (int i = 1; i <= n; i++) 23 Min[i][0] = a[i]; 24 for (int j = 1; (1 << j) <= n; j++) 25 for (int i = 1; i + (1 << j) - 1 <= n; i++) 26 Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]); 27 memset(dp, 127, sizeof(dp)); 28 dp[0] = 0; 29 for (int i = 1; i <= n; i++) { 30 dp[i] = dp[i - 1]+a[i]; 31 if (i - m >= 0) 32 dp[i] = min(dp[i], dp[i - m] + sum[i] - sum[i - m] - Q(i - m + 1, i)); 33 } 34 printf("%lld ", dp[n]); 35 }