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
下一篇: 草根创业的机会在哪里(互联网创业的思考)
推荐阅读
-
Codeforces Round #655 (Div. 2) A. Omkar and Completion
-
Codeforces Round #659 (Div. 2) A. Common Prefixes(字符串,思维)
-
A. Soldier and Bananas
-
Codeforces Round #686 (Div. 3) A. Special Permutation
-
Codeforces A. Sign Flipping (思维 / 构造) (Global Round 9)
-
codeforces A. Sum of Odd Integers
-
A. Add Odd or Subtract Even(思维题) Codeforces Round #624 (Div. 3)
-
Codeforces 1327 A. Sum of Odd Integers
-
codeforces A. Odd Selection
-
【Codeforces Global Round 7】A. Bad Ugly Numbers 题解