[Codeforces 940.E] Cashback（dp，数据结构，贪心）

题目

E. Cashback

time limit per test 2 seconds
memory limit per test 256 megabytes
input standard input
output standard output

Since you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount.
You are given an array a of length n and an integer c.
The value of some array b of length k is the sum of its elements except for the smallest. For example, the value of the array [3, 1, 6, 5, 2] with c = 2 is 3 + 6 + 5 = 14.
Among all possible partitions of a into contiguous subarrays output the smallest possible sum of the values of these subarrays.

Input

The first line contains integers n and c (1 ≤ n, c ≤ 100 000).
The second line contains n integers ai (1 ≤ ai ≤ 10^9) — elements of a.

Output

Output a single integer — the smallest possible sum of values of these subarrays of some partition of a.

Examples

Note

In the first example any partition yields 6 as the sum.
In the second example one of the optimal partitions is [1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10] with the values 2 and 90 respectively.
In the third example one of the optimal partitions is [2, 3], [6, 4, 5, 7], [1] with the values 3, 13 and 1 respectively.
In the fourth example one of the optimal partitions is [1], [3, 4, 5, 5, 3, 4], [1] with the values 1, 21 and 1 respectively.

解题思路

这当然是一道dp题。
我们先设$dp[i]$表示前$i$个数字划分后的最小代价，那么转移就是$dp[i]=min\{dp[k]+cal(k+1, i)\ |\ 1 \leqslant k < i\}$，其中$cal(l, r)$是计算$l$到$r$作为整体时的代价。
复杂度？$cal(l,r)$可以用multiset之类的做到$O(\log n)$完成，但是dp方程里面有两层循环，所以复杂度高达$O(n^2\log n)$，差远了。

怎么优化呢？这里我们可以发现一个贪心：划分的每一块长度要么是1，要么是c。证明：如果块的长度小于c，那么代价是所有值的和，与把这些值划分成一份一份的等价；如果块的长度大于c，我们把它们划分成几个长为c或1的块，答案一定不会更差（去除数量相同，但区间更小，更有机会去除掉大一点的数，手动模拟一下就知道了）。
综上所述，我们的dp长这样：

• dp状态：$dp[i]$表示前$i$个数字划分后的最小代价
• dp方程：$dp[i] = min\big(dp[i-1] + a[i], dp[i-c] + sum(i-c+1, i) - min(i-c+1, i)\big)$
  由于长为c的段只会去除最小的值，所以上文中的$cal()$变成了此处的$min()$
  sum(l,r)表示$l$到$r$的和，可以前缀和优化到$O(1)$
  min(l,r)表示$l$到$r$的最小值，由于$l$~$r$长度固定为c，所以可以单调队列$O(n)$的预处理出来
• dp顺序：由dp方程可知，$i$从小到大for即可
• 边界条件：$dp[0] = 0$

时间复杂度 $O(n)$

Code

#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

typedef long long LL;
const int N = 100005;
int n, c, hd, tl;
LL a[N], sum[N], mnC[N], dp[N];
pair<LL, int> q[N];

int main(){
    scanf("%d%d", &n, &c);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
        sum[i] = sum[i-1] + a[i];
        while(hd < tl && q[tl-1].first > a[i])  tl--;
        q[tl++] = make_pair(a[i], i);
        while(hd < tl && q[hd].second <= max(i - c, 0)) hd++;
        mnC[i] = q[hd].first;
    }
    memset(dp, 0x7f, sizeof dp);
    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i-1] + a[i];
        if(i - c >= 0)  dp[i] = min(dp[i], dp[i-c] + sum[i] - sum[i-c] - mnC[i]);
    }
    printf("%lld", dp[n]);
    return 0;
}