本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-21 22:09:24

一眼 dp （贪心）。

部分分 （有吗）：

我们通过思考发现贪心策略是不行的，那么我们考虑 dp。

设状态：

我们设 $f_{i,j}$ 为循环到第 $i$ 个球且选中了第 $i$ 个球，并有 $j$ 个球被删除能所得的最大价值（若取不到值便为负无穷）。
边界条件是 $f_{0,0}=0$，最后的答案是什么我们还需要思考一下：
故最后答案为：
$$ans=\max_{i=n-k}^n(f_i)$$

设状态转移方程：

那么我们可以寻找一个球 $p\ (j-1\le p\le i-1)$ 和一个值 $f_{p,j-1}$，也就是说我们假设倒数第二个没有被删除的球为 $p$，易得转移方程：
$$f_{i,j}=\max_{p=j-1,c_p\ne c_i}^{i-1}(f_{p,j-1})+v_i$$ 这样时间复杂度就是 $O(nk^2)$，考虑优化。

优化：

如果没有 $c_p\ne c_i$ 的限制的话，这道题就变得非常简单，只需要边维护 $f$ 数组，边计算最大值即可。
但这只是假设，有了这条限制我们该怎么办呢？
解决方法当然有，我们找到一个次大值 $p'$，使 $c_{p'}\ne c_p$ 即可。
为什么呢？

• 若 $c_p=c_i$，则 $c_{p'}\ne c_i$，$c_{p'}$ 为最优解。
• 若 $c_p\ne c_i$，则 $c_p$ 本身就为最优解。

那么问题又来了，如何转移（定义最大值为 $fmax$，次大值为 $smax$，结尾 $c$ 值为 $lst$，由于空间复杂度较大，故后面 $f$ 压掉第一维）？

• 若 $lst\ne c_j$，则：
  $f_j=fmax+v_j$，更新 $f_j$。
  若以前的 $f_j\ge fmax$：$smax=fmax,fmax=f_j,lst=c_j$。
  若 $f_j\ge smax$：$smax=f_j$。
• 若 $lst=c_j$，则：
  $f_j=smax+v_j$，更新 $f_j$。
  若 $f_j\ge fmax$：$fmax=f_j$。

这样，时间复杂度为 $O(nk)$，空间复杂度为 $O(n)$，可以通过。
代码：

#include<bits\/stdc++.h>
#define int long long
#define inl inline
#define INF 214748364721474836
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define rer(i,x,y,cmp) for(int i=x;i<=y&&cmp;++i)
#define T set<string>::iterator
using namespace std;
const int N=2e5+5;
int n,k,c[N],v[N],f[N],ans=-INF;
signed main(){
	fst;
	memset(f,-0x3f,sizeof(f));
	f[0]=0;
	cin>>n>>k;
	rep(i,1,n) cin>>c[i]>>v[i];
	rep(i,1,n-k){
		int first_max=f[i-1],second_max=-INF,copyc=c[i-1];
		rep(j,i,i+k){
			int copyf=f[j];
			if(c[j]!=copyc){
				f[j]=first_max+v[j];
				if(copyf>=first_max){
					second_max=first_max;
					first_max=copyf;
					copyc=c[j];
				}else if(copyf>=second_max) second_max=copyf;
			}else{
				f[j]=second_max+v[j];
				if(copyf>=first_max) first_max=copyf;
			}
		}
	}
	rep(i,n-k,n) ans=max(ans,f[i]);
	if(ans>=0) cout<<ans;
	else cout<<-1;
    return 0;
}