题目：给一个1-n的数字序列，某些数字被移除，请重新填写这些数字使得一奇一偶的对数足够少。
思路：dp[i][j][k][2]，表示考虑前i个数，有j个奇数数，k个偶数，且最后一位是奇、偶数的最小值
分类讨论：一、a[i]为0，即第i处数字空缺
dp[i][j][k][0]=min(dp[i−1][j][k−1][0],dp[i−1][j][k−1][1]+1)，若k>0
dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]),若j>0dp[i][j][k][1]=min(dp[i−1][j−1][k][0]+1,dp[i−1][j−1][k][1]),若j>0
二、若a[i]处数字不空缺
判断a[i]处是奇数还是偶数：
奇数：dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1])dp[i][j][k][1]=min(dp[i−1][j−1][k][0]+1,dp[i−1][j−1][k][1])
偶数：dp[i][j][k][0]=min(dp[i-1][j][k-1][1]+1,dp[i-1][j][k-1][0])dp[i][j][k][0]=min(dp[i−1][j][k−1][1]+1,dp[i−1][j][k−1][0])
当然，前几位奇数的个数确定后，偶数的个数同样也能确定
原文链接：https://www.ancode.club/index.php/2020/08/07/acm7/
1 #include<iostream> 2 #include<string.h> 3 #include<cmath> 4 #include<map> 5 using namespace std; 6 typedef long long ll; 7 const int INF=0x3f3f3f3f; 8 const int N=110; 9 int n; 10 int a[N]; 11 ll dp[N][N][N][2];//dp[i][j][k][2]，表示考虑前i个数，有j个奇数数，k个偶数，且最后一位是奇、偶数的最小值。 12 string s[1505]; 13 int main() { 14 ios::sync_with_stdio(false); 15 cin>>n; 16 //前n个数 有cnt0个偶数，cnt1个奇数 17 int cnt0=n/2; 18 int cnt1=n/2+n%2; 19 memset(dp,0x3f,sizeof(dp)); 20 for(int i=1;i<=n;++i){ 21 cin>>a[i]; 22 } 23 dp[0][0][0][0]=dp[0][0][0][1]=0; 24 for(int i=1;i<=n;i++){ 25 for(int j=0;j<=cnt1;++j){ 26 for(int k=0;k<=cnt0;++k){ 27 if(!a[i]){ 28 if(k>0) dp[i][j][k][0]=min(dp[i-1][j][k-1][0],dp[i-1][j][k-1][1]+1); 29 if(j>0) dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]); 30 }else{ 31 if(a[i]%2){ 32 if(j>0) dp[i][j][k][1]=min(dp[i-1][j-1][k][0]+1,dp[i-1][j-1][k][1]); 33 } 34 else { 35 if(k>0) dp[i][j][k][0]=min(dp[i-1][j][k-1][1]+1,dp[i-1][j][k-1][0]); 36 } 37 } 38 } 39 } 40 } 41 cout<<min(dp[n][cnt1][cnt0][0],dp[n][cnt1][cnt0][1])<<endl; 42 return 0; 43 }