链接
https://codeforces.com/contest/1287/problem/C
题意
一个长度为 $n$ 的不存在相同数的无序序列，已知其未被填完
求在填完后相邻两数奇偶性不同的对的个数的最小值
思路一
贪心
将整个串分为 $0$ 段和非 $0$ 段
若一个 $0$ 段两端都是偶数或都是奇数，都填偶数或都填奇数，否则贡献为 $2$
若一个 $0$ 段两端奇偶性不同，贡献为 $1$
若一个 $0$ 段只有一端，填与它拥有那一段奇偶性相同的数，否则贡献为 $1$
将拥有两端的 $0$ 段长度从小到大排序进行贪心
最后判断只有一端的 $0$ 段
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,a[N],b[2][N],t[2],c[3],ans;
pair<int,int> st,ed;
void init() {
if((n&1)==0) c[0]=c[1]=n/2;
else c[0]=n/2,c[1]=n/2+1;
}
void solve() {
int l=0,r=0,cnt=0;
int pre=1;
int f=0;
for(int i=1;i<=n;i++) {
if(a[i]==0) {
if(cnt==0) l=pre&1;
cnt++;
}
else {
c[a[i]&1]--;
if(a[i-1]!=0) {
if((a[i]&1)!=(a[i-1]&1)) ans++;
}
if(cnt) {
r=a[i]&1;
if(!a[1]&&!f) f=1,st={cnt,r};
else if(l==r) b[l][++t[l]]=cnt;
else ans++;
cnt=0;
}
pre=a[i];
}
}
if(cnt) ed={cnt,l};
sort(b[0]+1,b[0]+1+t[0]);
sort(b[1]+1,b[1]+1+t[1]);
for(int i=0;i<2;i++)
for(int j=1;j<=t[i];j++) {
if(c[i]>=b[i][j]) c[i]-=b[i][j];
else ans+=2;
}
if(c[st.second]>=st.first) c[st.second]-=st.first;
else ans++;
if(c[ed.second]<ed.first) ans++;
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
init();
for(int i=1;i<=n;i++) cin>>a[i];
solve();
return 0;
}
|
思路二
DP
一维：长度，二维：剩余偶数个数，三维：当前数奇偶性
界限：
当存在偶数且第一个数为0或偶数：$dp[1][n/2-1][0]=0$
当第一个数为 $0$ 或奇数：$dp[1][n/2][1]=0$
状态转移：
当前填偶数：$dp[i][j-1][0]=\min(dp[i][j-1][0],dp[i-1][j][k]+(k==1))$
当前填奇数：$dp[i][j][1]=\min(dp[i][j][1],dp[i-1][j][k]+(k==1))$
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,a[N],dp[N][N][2];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
memset(dp,0x3f,sizeof dp);
if(n>1&&(a[1]==0||a[1]%2==0)) dp[1][n/2-1][0]=0;
if(a[1]==0||a[1]%2==1) dp[1][n/2][1]=0;
for(int i=2;i<=n;i++)
for(int j=0;j<=n/2;j++)
for(int k=0;k<2;k++) {
if(j>0&&(a[i]==0||a[i]%2==0)) dp[i][j-1][0]=min(dp[i][j-1][0],dp[i-1][j][k]+(k==1));
if(i+j-1<n&&(a[i]==0||a[i]%2==1)) dp[i][j][1]=min(dp[i][j][1],dp[i-1][j][k]+(k==0));
}
cout<<min(dp[n][0][0],dp[n][0][1])<<endl;
return 0;
}
|