fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define inf 1e5
  3. #define mod 1000000007
  4. #define pb push_back
  5. #define ll long long int
  6. #define ld long double 
  7. using namespace std;
  8. int main(void){
  9. 	int i,j,k,n,l;
  10. 	cin>>n;
  11. 	int a[n];
  12. 	int o=(n+1)/2,e=n/2;
  13. 	for(i=0;i<n;i++){
  14. 		cin>>a[i];
  15. 	}
  16. 	int dp[n+5][o+5][e+5][5];
  17. 	for(i=0;i<=n;i++){
  18. 		for(j=0;j<=o;j++){
  19. 			for(k=0;k<=e;k++){
  20. 				dp[i][j][k][0]=inf;
  21. 				dp[i][j][k][1]=inf;
  22. 			}
  23. 		}
  24. 	}
  25. 	if(a[0]==0){
  26. 		dp[1][1][0][1]=0;
  27. 		dp[1][0][1][0]=0;
  28. 	}
  29. 	else{
  30. 		if(a[0]%2==0)
  31. 			dp[1][0][1][0]=0;
  32. 		else
  33. 			dp[1][1][0][1]=0;
  34. 	}
  35. 	for(i=2;i<=n;i++){
  36. 		if(a[i-1]==0){
  37. 			for(j=0;j<=o;j++){
  38. 				for(k=0;k<=e;k++){
  39. 					if(j+k==i){
  40. 						if(j==0)
  41. 						dp[i][j][k][0]=dp[i-1][j][k-1][0];
  42. 						else if(k==0)
  43. 						dp[i][j][k][1]=dp[i-1][j-1][k][1];
  44. 						else{
  45. 							if(k==1){
  46. 							dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][1]+1);
  47. 							dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]);
  48. 							}
  49. 							else
  50. 							dp[i][j][k][0]=min(dp[i-1][j][k-1][0],dp[i-1][j][k-1][1]+1);
  51. 							if(j==1){
  52. 							dp[i][j][k][1]=min(dp[i][j][k][1],dp[i-1][j-1][k][0]+1);
  53. 							dp[i][j][k][0]=min(dp[i-1][j][k-1][0],dp[i-1][j][k-1][1]+1);
  54. 							}
  55. 							else
  56. 							dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]);
  57. 						}
  58. 				}
  59. 			}
  60. 		}
  61. 		}
  62. 		else{
  63. 			if(a[i-1]%2==0){
  64. 				for(j=0;j<=o;j++){
  65. 				for(k=0;k<=e;k++){
  66. 					if(j+k==i){
  67. 						if(j==0)
  68. 						dp[i][j][k][0]=dp[i-1][j][k-1][0];
  69. 						else{
  70. 							if(k==1)
  71. 							dp[i][j][k][0]=dp[i-1][j][k-1][1]+1;
  72. 							else
  73. 							dp[i][j][k][0]=min(dp[i-1][j][k-1][0],dp[i-1][j][k-1][1]+1);
  74. 						}
  75. 				}
  76. 			}
  77. 		}
  78.  
  79. 	}
  80. 	else{
  81. 		for(j=0;j<=o;j++){
  82. 				for(k=0;k<=e;k++){
  83. 					if(j+k==i){
  84. 						if(k==0)
  85. 						dp[i][j][k][1]=dp[i-1][j-1][k][1];
  86. 						else{
  87. 							if(j==1)
  88. 							dp[i][j][k][1]=dp[i-1][j-1][k][0]+1;
  89. 							else
  90. 							dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]);
  91. 						}
  92. 				}
  93. 			}
  94. 		}
  95. 	}
  96. }
  97. }
  98. if(a[n-1]==0)
  99. cout<<min(dp[n][o][e][0],dp[n][o][e][1])<<endl;
  100. else
  101. cout<<dp[n][o][e][a[n-1]%2]<<endl;
  102. }
  103.  
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
5
0 5 0 2 3
stdout
copy 
2
https://ideone.com/YgCQKK
language:
C++14 (gcc 8.3)
created:
3 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!