A. Garland_IOS_移动技术网

https://codeforces.com/problemset/problem/1286/A

//  cin.tie(0);std::ios::sync_with_stdio(false);
//  LL n;cin>>n;
//  for(LL i=1;i<=n;i++){
//  	cin>>a[i];
//  }
//  memset(dp,0x3f,sizeof(dp));
//  dp[1][1]=dp[1][0]=0;
//  for(LL i=2;i<=n;i++){
//  	if(a[i]%2==1){
//  		if(a[i-1]%2==1){
//  			dp[i][1]=dp[i-1][1];	
//		}
//		else if(a[i-1]%2==0&&a[i-1]!=0){
//			dp[i][1]=dp[i-1][0]+1;
//		}
//		else if(a[i-1]==0){
//			dp[i][1]=min(dp[i-1][1],dp[i-1][0]+1);
//		}
//	}
//	else if(a[i]!=0&&a[i]%2==0){
//		if(a[i-1]%2==1){
//			dp[i][0]=dp[i-1][1]+1;
//		}
//		else if(a[i-1]%2==0&&a[i-1]!=0){
//			dp[i][0]=dp[i-1][0];
//		}
//		else if(a[i-1]==0){
//			dp[i][0]=min(dp[i-1][0],dp[i-1][1]+1);
//		}
//	}
//	else if(a[i]==0){
//		 if(a[i-1]%2==1){
//		 	dp[i][1]=min(dp[i][1],dp[i-1][1]);
//		 	dp[i][0]=min(dp[i][0],dp[i-1][0]+1);
//		 }
//		 else if(a[i-1]%2==0&&a[i-1]!=0){
//		 	dp[i][1]=min(dp[i][1],dp[i-1][0]+1);
//		 	dp[i][0]=min(dp[i][0],dp[i-1][0]);
//		 }
//		 else if(a[i-1]==0){
//		 	dp[i][1]=min(dp[i][1],min(dp[i-1][1],dp[i-1][0]+1));
//		 	dp[i][0]=min(dp[i][0],min(dp[i-1][0],dp[i-1][1]+1)); 
//		 }
//	}
//	cout<<"dp["<<i<<"][0]="<<dp[i][0]<<endl;
//	cout<<"dp["<<i<<"][1]="<<dp[i][1]<<endl; 
//  }
//  cout<<min(dp[n][1],dp[n][0])<<endl;
//

好了dp状态假了。因为我忘了这题的固定点的奇偶要记录的。重新dp。

dp[i][o][j][0/1]:考虑前i位，用了o个偶数，用了j个奇数，第i位填的是偶数/奇数的最小数量

转移看当前位有没有占据，分两种，然后看当前位奇偶和上一位奇偶，讨论一下。

可能越界的话在转移前写个 if(j) if(o)

然后耐心dp,这题挺考验的。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=120;
typedef long long LL;
LL a[maxn];
LL dp[maxn][maxn][maxn][3],num[2];
//考虑前i位，用了o个偶数，用了j个奇数，第i位填的是偶数/奇数的最小数量 
int main(void)
{
   LL n;cin>>n;
   for(LL i=1;i<=n;i++){
   	   cin>>a[i];
  	   if(a[i]==0) {a[i]=-1;continue;}//负数取模负数	  
   	   if(a[i]%2==1) num[1]++;
   	   else if(a[i]%2==0) num[0]++;
   } 
   num[1]=(n&1?n/2+1:n/2)-num[1];num[0]=n/2-num[0];//剩下的能填的奇数和偶数
   memset(dp,0x3f,sizeof(dp));
   dp[0][0][0][0]=dp[0][0][0][1]=0;
   if(a[1]==-1){//第一个没填 
   	if(num[0]) dp[1][1][0][0]=0;
   	
   	if(num[1]) dp[1][0][1][1]=0;
   } 
   else if(a[1]%2==1) dp[1][0][0][1]=0;
   else if(a[1]%2==0)dp[1][0][0][0]=0;
   
   for(LL i=2;i<=n;i++){
   	 if(a[i]!=-1){//如果当前位填了
		if(a[i]&1){//如果当前位是奇数 
			for(LL o=0;o<=num[0];o++)
   	 		for(LL j=0;j<=num[1];j++){
				dp[i][o][j][1]=min(dp[i][o][j][1],dp[i-1][o][j][1]);//上一位是奇数 
				dp[i][o][j][1]=min(dp[i][o][j][1],dp[i-1][o][j][0]+1);//上一位是偶数	
			}
		} 
		else{//如果当前位是偶数 
			for(LL o=0;o<=num[0];o++)
			for(LL j=0;j<=num[1];j++){
				dp[i][o][j][0]=min(dp[i][o][j][0],dp[i-1][o][j][1]+1);//上一位是奇数 
				dp[i][o][j][0]=min(dp[i][o][j][0],dp[i-1][o][j][0]);//上一位是偶数 
			}
		}
	 }  
	 else{//如果当前位是空 
	 	for(LL o=0;o<=num[0];o++)
	 	for(LL j=0;j<=num[1];j++){
	 	if(j)	dp[i][o][j][1]=min(dp[i][o][j][1],dp[i-1][o][j-1][0]+1);//当前填奇数,上一位是偶数 
		if(j)	dp[i][o][j][1]=min(dp[i][o][j][1],dp[i-1][o][j-1][1]);//当前填奇数，上一位是奇数 
		if(o)	dp[i][o][j][0]=min(dp[i][o][j][0],dp[i-1][o-1][j][0]);//当前填偶数，上一位是偶数 
		if(o)	dp[i][o][j][0]=min(dp[i][o][j][0],dp[i-1][o-1][j][1]+1);//当前填偶数，上一位是奇数 
		}
	 }
   }
   cout<<min(dp[n][num[0]][num[1]][1],dp[n][num[0]][num[1]][0])<<endl;
return 0;
}

本文地址：https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108133314