题解 CodeForces 940E Cashback

1. 题面描述

题目链接

给定长为 \(n\) 的序列和一个整数 \(c\)，你需要将其分为若干段。

对于每一段，若其长度为 \(k\)，则可以删除其中前 \(\lfloor\frac{k}{c}\rfloor\) 小的数。

最小化删除后的序列和。

\(1\le n,c\le10^5\)，\(1\le a[i]\le10^9\)，其中 \(a[i]\) 表示第 \(i\) 个数的值。

2. 分析

看上去不是很可做的样子，事出反常必有妖，于是观察特殊性质和结论，尝试转化题目。

首先，考虑长度 \(1\le k<c\) 的一段。因为其无法删除任何数，我们完全可以将其看作长度为 \(1\) 的 \(k\) 段，不会影响答案。

对于长度为 \(k\) 的段，我们只需按题意要求删掉其中最小的数即可。

考虑长度 \(>k\) 的段，简单情况即为长度为 \(k+1\) 的段。

对于长度为 \(k+1\) 的段，我们可以沿用上面的思路，将其分为 \(1\) 个长度为 \(k\) 的段和 \(1\) 个长度为 \(1\) 的段。发现这样分割一段方案一定不会让答案变得更劣，可能使答案变得更优。因为对于一个段，随着其长度的增加，其最小值一定为单调不升的，然而我们希望最小值尽量大。

于是对于我们来说，在允许删数的情况下，段的长度越短越好（读者可以思考 \(k=2c\) 的情况，可以帮助理解）。

因此，对于任意一个序列，我们可以通过将其分为若干长度为 \(1\) 的部分和若干长度为 \(k\) 的部分以获得最优解（一些部分长度为 \(k\) 是为了使答案最优，一些部分长度为 \(1\) 是为了简化问题）。

至此，问题已经被我们简化完毕，对于答案的求解可以使用动态规划。

设 \(f[i]\) 表示分好前 \(i\) 段时可以获得的最优答案，于是状态转移方程：

\(f[i]=min\{f[i-1]+a[i],f[i-c]+\sum_{j=i-c+1}^{i}a[j]-min_{j=i-c+1}^{i}a[j]\}\)。

初值 \(f[0]=0\)。

答案 \(ans=f[n]\)。

转移方程中的区间可以通过前缀和优化，区间 min 可以通过单调队列或 ST 表优化。

最优时间复杂度 \(O(n)\)。

3. 代码

注：作者在区间 min 部分使用了 ST 表，所以下述代码时间复杂度为 \(O(nlogn)\)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;

int n,c;
int st[N][20],lg[N];
ll sum[N],f[N];

inline int query(int l,int r) {
	int k=lg[r-l+1];
	return min(st[l][k],st[r-(1<<k)+1][k]);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>c;
	for (int i=1; i<=n; i++) {cin>>st[i][0]; sum[i]=sum[i-1]+st[i][0];}
	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=2; i<=n; i++) lg[i]=lg[i>>1]+1;
	memset(f,0x3f,sizeof f);
	f[0]=0;
	for (int i=1; i<=n; i++) {
		f[i]=f[i-1]+st[i][0];
		if (i>=c) f[i]=min(f[i],f[i-c]+sum[i]-sum[i-c]-query(i-c+1,i));
	}
	cout<<f[n]<<'\n';
	return 0;
}

本文完。