↓Skip to main content
  1. Posts/

CodeForces-1286A Garland

·2 mins·
Table of Contents

CodeForces-1286A Garland #

题目大意 #

有一个由 $1, 2, …, n$ 的排列, 其中一部分元素被删除了 (用 $0$ 表示) . 在所有可能的排列中, 输出奇偶性不同的相邻元素对的最小数量.

Solution 1 #

用 $dp[i][j][k][l]$ 表示 $p_0, …, p_i$ , 有 $j$ 个奇数, $k$ 个偶数, 最后一个元素奇偶性为 $l$ 的所有排列中, 不同的相邻元素对的最小数量. 利用动态规划计算. 代码如下:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int& v : a) {
        cin >> v;
    }
    int dp[n][(n + 1) / 2 + 1][n / 2 + 1][2];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (n + 1) / 2 + 1; j++) {
            for (int k = 0; k < n / 2 + 1; k++) {
                for (int l = 0; l < 2; l++) {
                    dp[i][j][k][l] = 1e9;
                }
            }
        }
    }
    if (a[0] == 0) {
        dp[0][1][0][1] = 0;
        dp[0][0][1][0] = 0;
    } else if (a[0] & 1) {
        dp[0][1][0][1] = 0;
    } else {
        dp[0][0][1][0] = 0;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < (n + 1) / 2 + 1; j++) {
            for (int k = 0; k < n / 2 + 1; k++) {
                if (a[i] == 0) {
                    if (j > 0) {
                        dp[i][j][k][1] =
                            min(dp[i][j][k][1], dp[i - 1][j - 1][k][1]);
                        dp[i][j][k][1] =
                            min(dp[i][j][k][1], dp[i - 1][j - 1][k][0] + 1);
                    }
                    if (k > 0) { 
                        dp[i][j][k][0] =
                            min(dp[i][j][k][0], dp[i - 1][j][k - 1][1] + 1);
                        dp[i][j][k][0] =
                            min(dp[i][j][k][0], dp[i - 1][j][k - 1][0]);
                    }
                } else if (a[i] & 1) {
                    if (j > 0) {
                        dp[i][j][k][1] =
                            min(dp[i][j][k][1], dp[i - 1][j - 1][k][1]);
                        dp[i][j][k][1] =
                            min(dp[i][j][k][1], dp[i - 1][j - 1][k][0] + 1);
                    }
                } else {
                    if (k > 0) {
                        dp[i][j][k][0] =
                            min(dp[i][j][k][0], dp[i - 1][j][k - 1][1] + 1);
                        dp[i][j][k][0] =
                            min(dp[i][j][k][0], dp[i - 1][j][k - 1][0]);
                    }
                }
            }
        }
    }
    int ans = 1e9;
    for (int j = 0; j < (n + 1) / 2 + 1; j++) {
        for (int l = 0; l < 2; l++) {
            ans = min(ans, dp[n - 1][j][n - j][l]);
        }
    }
    cout << ans << endl;
    return 0;
}
↑