欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

A. Garland

程序员文章站 2022-06-25 15:02:00
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<...

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

相关标签: dp 线性dp