我要评论思路
- 贪心有点复杂，这里直接用dp，思路清晰得多
- dp[i][j][0//1]表示枚举到第i个位置，已经把j个奇数填上去了（这里不包括原来就再序列里面的奇数），并且当前位置为奇数（0）/偶数（1）的代价
- 转移方程：
- ①：如果当前位置已经有数字了，那么就根据数字的奇偶性不同转移
- 奇数 ：dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]+1);
偶数 ：dp[i][j][1]=min(dp[i-1][j][0]+1,dp[i-1][j][1]);
*如果当前位置没有数字，就枚举一下是填奇数还是偶数， - 奇数 ：dp[i][j][0]=min(dp[i-1][j-1][1]+1,dp[i-1][j-1][0]);
偶数 ：dp[i][j][1]=min(dp[i-1][j][1],dp[i-1][j][0]+1);
这里还要判断一下，是否由奇数可以填、偶数可以填
- 奇数 ：dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]+1);
- ①：如果当前位置已经有数字了，那么就根据数字的奇偶性不同转移
代码
#include<bits/stdc++.h>
using namespace std;
int a[150];
int dp[150][150][2];
int sum[150];
int main()
{
int n;
cin >> n;
int num=0;
int count=0;
for(int i=1;i<=n;i++){
cin >> a[i];
if(a[i]==0)num++;
if(a[i]%2)count++;
sum[i]=num;
}
count=(n+1)/2-count;
memset(dp,0x3f3f3f,sizeof dp);
if(a[1]){
if(a[1]%2)dp[1][0][0]=0;
else dp[1][0][1]=0;
}
else{
dp[1][1][0]=0;
dp[1][0][1]=0;
}
for(int i=2;i<=n;i++){
for(int j=0;j<=count;j++){
if(a[i]){
if(a[i]%2)dp[i][j][0]=min(dp[i-1][j][0],dp[i-1][j][1]+1);
else dp[i][j][1]=min(dp[i-1][j][0]+1,dp[i-1][j][1]);
}else{
if(j>0)dp[i][j][0]=min(dp[i-1][j-1][1]+1,dp[i-1][j-1][0]);
if(sum[i]-j<=num-count)dp[i][j][1]=min(dp[i-1][j][1],dp[i-1][j][0]+1);
}
}
}
cout << min(dp[n][count][0],dp[n][count][1]);
}
本文地址：https://blog.csdn.net/weixin_45080867/article/details/107893696
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论