绝对没坑*2

#include<bits/stdc++.h>
using namespace std;
const int N=1000+5,W=30+5;
int a[N],dp[N][W],val;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t,w;
	cin>>t>>w;
	for(int i=1;i<=t;i++){
		cin>>a[i];
	}
	for(int i=0;i<=t;i++){
		for(int j=0;j<=w;j++){
			dp[i][j]=-0x3f3f3f3f;
		}
	}
	dp[0][0]=0;
	for(int i=1;i<=t;i++){
		for(int j=0;j<=w&&j<=i;j++){
			if(j%2+1==a[i]){
				val=1;
			}
			else{
				val=0;
			}
			dp[i][j]=dp[i-1][j]+val;
			if(j>=1){
				dp[i][j]=max(dp[i][j],dp[i-1][j-1]+val);
			}
		}
	}
	int ans=0;
	for(int j=0;j<=w;j++){
		ans=max(ans,dp[t][j]);
	}
	cout<<ans<<endl;
	return 0;
}

时隔2年和一半，补齐DP与记搜