不得不說這道 dp 既考察對時間復雜度方面的優化，也要考慮對空間方面的優化。

題意

首先從暴力說起：

首先既然讓我們刪除 \(k\) 個數，也就是說保留 \(N-k\) 個數。
顯然可以 dfs 枚舉子集加剪枝優化(不過剪不剪的好像沒啥區別)，這樣做是 \(O(2^N)\) 估計只能過樣例。

代碼：

//tomxi
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5; 
bitset<N> v;
int val[N],mx=-1,col[N],n,k;
inline void dfs(int x,int K){
	if(K>k) return;
	if(K+(n-x+1)<k) return;
	if(x==n+1){
		if(K!=k) return;
		int pos=-1,s=0;
		for(int i=1;i<=n;i++){
			if(v[i]){
				if(col[i]==pos) return;
				pos=col[i];
				s+=val[i];
			}
		}
		mx=max(mx,s);
		return;
	}
	for(int i=0;i<=1;i++){
		v[x]=i;
		dfs(x+1,K+(!i));
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>col[i]>>val[i];
	dfs(1,0);
	cout<<mx;
	return 0;
}
//tomxi

發現如果一個數選肯定是比不選要優的所以我們可以考慮盡可能的選第 \(i\) 個數，因此考慮 dp。
暴力的 dp:
一個最最最暴力的做法就是定義 \(f_{i,j}\) 表示在前 \(i\) 個數中選了 \(j\) 個數且第 \(i\) 個數必須選，那么一個很顯然的轉移方程就是 \(f_{i,j} = val_i + \max_{x=1}^{i-1} f_{x,j-1}\) 。這樣做很顯然是 \(O(N^2K)\) 的，過不了。

代碼：

//tomxi
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e3+5;
const int K=2e3+5;
int f[N][K]; 
int col[N],val[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n,k;
	cin>>n>>k;
	int maxn=0,tm=0;
	for(int i=1;i<=n;i++) cin>>col[i]>>val[i];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n-k;j++){
			maxn=0;int stm=1;
			f[i][j]=val[i];
			for(int p=1;p<i;p++){
				if(col[p]!=col[i])maxn=max(maxn,f[p][j-1]);
				if(col[p]!=col[i]) stm++;
			}
			tm=max(tm,stm);
			f[i][j]+=maxn;
		}
	}
	int mx=0;
	if(tm<n-k){
		cout<<-1;return 0;
	}
	for(int i=1;i<=n;i++) mx=max(mx,f[i][n-k]);
	cout<<mx;
	return 0;
}
//tomxi

時間復雜度方面優化 dp:
其實我們發現我們選的區間都是連續的區間，因此可以考慮用數據結構來優化它，固然考慮線段樹，但是因為如果最大值的 col[] 與 col[i] 相同的話就要考慮使用次大值了，這樣做的話要考慮區間最大值和嚴格區間次大值，處理起來相當麻煩，關鍵是還過不了，時間復雜度是 \(O(Nk\log_2N)\)
但其實并不需要這么麻煩，在仔細觀察一下，可以發現所取的區間不光是連續的，而且還是從 1 到 i 的，因此我們可以用兩個變量來儲存所對應的最大值，次大值，最大值的位置，次大值的位置。

空間方面的優化 dp:

因為 \(k\leq 500\) 所以 \(N-k\) 會很大，因此如果我們開二維的數組會到達 \(O(4\times 10^{10})\) 是不行的，因此考慮用滾動數組優化它。

代碼：

//tomx
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=2e5+5;
int n,k,col[N],val[N];
ll f[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);cout.tie(nullptr);
  cin>>n>>k;
  for(int x=1;x<=n;++x) cin>>col[x]>>val[x];
  memset(f,-1e18,sizeof(f));
  for (int y=1;y<=n-k;++y) {
    ll m=f[y-1],_m=-1e18;
    int cm=col[y-1];
    for (int z=y;z<=y+k;++z){
      ll M=f[z];
      if(col[z]!=cm) {
        f[z]=m+val[z];
        if(M>=m){
          _m=m,m=M,cm=col[z];
        }else if(M>_m){
          _m=M;
        }
      }else{
        f[z]=_m+val[z];
        if(M>m){
          m=M;
        }
      }
    }
  }
  ll ans=-1;
  for(int i=n-k;i<=n;++i) {
    ans=max(ans,f[i]);
  }
  cout<<ans;
  return 0;
}