Codeforces Round #612 (Div. 2) C

作者: frans4x | 来源:发表于2020-01-09 10:12 被阅读0次

Codeforces Round #612 (Div. 2) C. Garland

Vadim loves decorating the Christmas tree, so he got a beautiful garland as a present. It consists of n light bulbs in a single row. Each bulb has a number from 1 to n (in arbitrary order), such that all the numbers are distinct. While Vadim was solving problems, his home Carp removed some light bulbs from the garland. Now Vadim wants to put them back on.

Vadim wants to put all bulb back on the garland. Vadim defines complexity of a garland to be the number of pairs of adjacent bulbs with numbers with different parity (remainder of the division by ). For example, the complexity of 1 4 2 3 5 is 2 and the complexity of 1 3 5 7 6 4 2 is .

No one likes complexity, so Vadim wants to minimize the number of such pairs. Find the way to put all bulbs back on the garland, such that the complexity is as small as possible.

Input

The first line contains a single integer — the number of light bulbs on the garland.

The second line contains n integers — the number on the bulb, or if it was removed.

Output

Output a single number — the minimum complexity of the garland.

Examples

input

output

input

output

Note

In the first example, one should place light bulbs as 1 5 4 2 3. In that case, the complexity would be equal to 2, because only (5,4)and (2,3) are the pairs of adjacent bulbs that have different parity.

In the second case, one of the correct answers is 1 7 3 5 6 4 2.

思路：动态规划

一维：长度，

二维：剩余偶数个数

三维：当前数奇偶性

界限：

当存在偶数且第一个数为0或偶数：
当第一个数为 00 或奇数：

状态转移：

当前填偶数：
当前填奇数：

AC:

<pre mdtype="fences" cid="n13" lang="cpp" class="md-fences md-end-block md-fences-with-lineno ty-contain-cm modeLoaded" spellcheck="false" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px 0px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;"> #include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
int n, a[maxn], dp[maxn][maxn][2];
int main(){
ios_base::sync_with_stdio(0);
int n;
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] % 2 == 1 || a[1] == 0)
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;
}</pre>

网友评论

本文标题：Codeforces Round #612 (Div. 2) C

本文链接：https://www.haomeiwen.com/subject/lrfyactx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

Codeforces Round #612 (Div. 2) C

Codeforces Round #612 (Div. 2) C. Garland

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读