目前思路感觉有点问题。

大概是贪心+背包。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int M = 2e5 + 5;
int c[M], v[M], n, k, ans;
int C[M], V[M];
int dp[505];

int l[M], r[M], sum[M], tot = 1;
int N;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> k;
	for(int i = 1; i <= n; ++i)
		cin >> c[i] >> v[i], sum[i] = sum[i - 1] + v[i];
	
	l[1] = 1, r[1] = 1;
	for(int i = 2; i <= n; ++i) {
		if(c[i] == c[i - 1])
			++r[tot];
		else
			l[++tot] = i, r[tot] = i;
	}
	
	r[tot] = n;
	
		
	
	for(int i = 1; i <= tot; ++i) {
		if(r[i] - l[i] + 1 > 1) {
			V[++N] = r[i] - l[i], C[N] = sum[r[i] - 1] - sum[l[i]] + min(v[r[i]], v[l[i]]);
		}
	}
	
	if(N == 0) {
		sort(v + 1, v + 1 + n);
		for(int i = 1; i <= k; ++i)	
			ans += v[i];
		cout << sum[n] - ans;
		return 0;
	}
	
//	for(int i = 1; i <= N; ++i)
//		cout << V[i] << ' ' << C[i] <<'\n';
	
	
	memset(dp, 0x3f, sizeof dp), dp[0] = 0;
	for(int i = 1; i <= N; ++i) {
		for(int j = k; j >= V[i]; --j)
			dp[j] = min(dp[j], dp[j - V[i]] + C[i]);
	}
	if(dp[k] > 1e9)
		return cout << -1, 0;
	cout << sum[n] - dp[k];
	return 0;
}

WA 10

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int M = 2e5 + 5;
int c[M], v[M], n, k, ans;
int C[M], V[M];
int dp[505];

int l[M], r[M], id[M], sum[M], tot = 1;
int N;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> k;
	for(int i = 1; i <= n; ++i)
		cin >> c[i] >> v[i], sum[i] = sum[i - 1] + v[i];
	
	l[1] = 1, r[1] = 1, id[1] = c[1];
	for(int i = 2; i <= n; ++i) {
		if(c[i] == c[i - 1])
			++r[tot];
		else
			l[++tot] = i, r[tot] = i, id[tot] = c[i];
	}
	
	r[tot] = n;
	
		
	
	for(int i = 1; i <= tot; ++i) {
		if(r[i] - l[i] + 1 > 1) {
			V[++N] = r[i] - l[i], C[N] = sum[r[i] - 1] - sum[l[i]] + min(v[r[i]], v[l[i]]);
		}
		if(1 < i && i < tot && id[i - 1] == id[i + 1])
			V[++N] = r[i + 1] - l[i - 1], C[N] = sum[r[i + 1] - 1] - sum[l[i - 1]] + min(v[r[i + 1]], v[l[i - 1]]);
		else if(id[i - 1] != id[i + 1])
			V[++N] = r[i] - l[i] + 1, C[N] = sum[r[i]] - sum[l[i] - 1];
	}
	
//	if(N == 0) {
//		sort(v + 1, v + 1 + n);
//		for(int i = 1; i <= k; ++i)	
//			ans += v[i];
//		cout << sum[n] - ans;
//		return 0;
//	}
	
//	for(int i = 1; i <= N; ++i)
//		cout << V[i] << ' ' << C[i] <<'\n';
	
	
	memset(dp, 0x3f, sizeof dp), dp[0] = 0;
	for(int i = 1; i <= N; ++i) {
		for(int j = k; j >= V[i]; --j)
			dp[j] = min(dp[j], dp[j - V[i]] + C[i]);
	}
	if(dp[k] > 1e9)
		return cout << -1, 0;
	cout << sum[n] - dp[k];
	return 0;
}

乱搞 WA 17