[Codeforces 940.E]Cashback（动态规划，单调队列，贪心）

发表于 更新于 分类于 ， ， ， ，
Codeforces 940E. Cashback

题目

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 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 $\lfloor \frac{k}{c} \rfloor$ 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≤100000$).
The second line contains n integers ai ($1≤a_i≤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

input output
3 5
1 2 3		 6
12 10
1 1 10 10 10 10 10 10 9 10 10 10		 92
7 2
2 3 6 4 5 7 1		 17
8 4
1 3 4 5 5 3 4 1		 23

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 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;
}