fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,a[1001];
  4. int has[1001];
  5. int dp[101][101][101];
  6. int cal(int i){
  7. 	if(i==0)return 0;
  8. 	return (a[i-1]%2)!=(a[i]%2);
  9. }
  10. int fun(int i,int e,int o){
  11. 	if(i==n){
  12. 		return 0;
  13. 	}
  14. 	//cout<<"hello\n";
  15. 	 if(dp[i][e][o]!=-1)return dp[i][e][o];
  16. 	else if(a[i]==0){
  17. 		int x,y;
  18. 		if(e>=1){
  19. 			a[i]=2;
  20. 			x=cal(i)+fun(i+1,e-1,o);
  21. 			a[i]=0;
  22. 		}
  23. 		else{
  24. 			x=1000;
  25. 		}
  26. 	    if(o>=1){
  27. 	    	a[i]=1;
  28. 	    	y=cal(i)+fun(i+1,e,o-1);
  29. 	    	a[i]=0;
  30. 	    }
  31. 	    else{
  32. 	    	y=1000;
  33. 	    }
  34. 	      return dp[i][e][o]=min(x,y);
  35. 	}
  36. 	else{
  37. 		return dp[i][e][o]=cal(i)+fun(i+1,e,o);
  38. 	}
  39. }
  40. int main() {
  41. 	cin>>n;
  42. 	int even=0,odd=0;
  43. 	for(int i=0;i<n;i++){
  44. 		cin>>a[i];
  45. 		has[a[i]]++;
  46. 	}
  47. 	for(int i=1;i<=n;i++){
  48. 		if(has[i]==0){
  49. 			if(i%2==1){
  50. 				odd++;
  51. 			}
  52. 			else{
  53. 				even++;
  54. 			}
  55. 		//	cout<<i<<endl;
  56. 		}
  57. 	}
  58.  
  59. 	for(int i=0;i<=n;i++){
  60. 		for(int j=0;j<=even;j++){
  61. 			for(int k=0;k<=odd;k++){
  62. 				dp[i][j][k]=-1;
  63. 			}
  64. 		}
  65. 	}
  66. 	cout<<fun(0,even,odd)<<endl;
  67.  
  68. 	return 0;
  69. }
Success #stdin #stdout 0s 4452KB
comments (?)
stdin
copy 
5
0 5 0 2 3
stdout
copy 
3
https://ideone.com/QqdfXz
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!