D - Moving Pieces on Line¶

题意¶

$X=10^{100}$ として、各整数 $−X\le i\le X$ に対応する頂点があり、 $−X\le i\le X−1$ について頂点 $i,i+1$ を結ぶ無向辺 (以降、辺 ${i,i+1}$ と呼ぶ) があるグラフがあります。

このグラフの辺は初めすべて赤く塗られています。また、 $N$ 個のコマがあり、 $i$ 個目のコマは頂点 $a_i$ に置かれています。

maroon 君は次の操作を行うことができます。

コマを $1$ つ選ぶ。このコマが頂点 $i$ にあるとき、コマを頂点 $i−1$ または頂点 $i+1$ に動かし、通った辺を、現在の色が赤なら青、青なら赤に塗り替える。

操作の過程で、同じ頂点に複数のコマが存在しても構いません。

maroon 君はこれから上記の操作を $0$ 回以上繰り返して、辺の色の組合せを目的の状態にしたいと思っています。目的の状態は偶数 $K$ と、 $K$ 個の整数 $t_1<t_2<\ldots<t_K$ で表され、 $i<t_1$ について辺 ${i,i+1}$ は赤、 $t_1\le i<t_2$ について辺 ${i,i+1}$ は青、……、 $t_K\le i$ について辺 ${i,i+1}$ は赤　という状態です。より正確には、各奇数 $j=1,3,\ldots,K−1$ に対して、 $t_j\le i<t_{j+1}$ を満たす $i$ について辺 ${i,i+1}$ は青で、それ以外の辺はすべて赤です。

maroon 君が辺の色の組合せを目的の状態にするために必要な操作回数の最小値を求めてください。また、そのような操作が不可能であるなら $−1$ を出力してください。

解析¶

设第 $i$ 个駒被移动到了 $b_i$ ，利用差分的思想，我们令 $s[a_i]\gets s[a_i]+1,s[b_i]\gets s[b_i]+1$ (孰加孰减其实不重要，因为我们只关心 parity)，最后判断 $s$ 的每个前缀和的 parity 即可。

那么，对于每个 $j\in\{t_i\}$ ，我们都要求 $2\nmid S[j]$ ，而对于其余的数则要求 $2\mid S_j$ 。这样，我们先计算 $T=\complement_{\{t_i\}\cup\{a_i\}}(\{t_i\}\cap\{a_i\})$ ，则对于合法的移动，一定有 $\{b_i\}=T$ (其实这里用集合不太正确)。

若 $|T|> N$ 或 $|T|\not\equiv N\bmod2$ ，则无解。否则，用动态规划匹配 $a_i$ 与 $b_i$ 。

实现¶

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 5e3 + 19;

int n, k;

std::vector<int> parity_set(const std::vector<int> &a){
    std::vector<int> b(a), res;
    std::sort(b.begin(), b.end());
    b.resize(std::unique(b.begin(), b.end()) - b.begin());
    std::vector<bool> c(b.size());
    for(int i : a)
        c[std::lower_bound(b.begin(), b.end(), i) - b.begin()].flip();
    for(int i = 0; i < (int)c.size(); ++i)
        if(c[i])
            res.push_back(b[i]);
    return res;
}

std::vector<int> a, T;
ll dp[maxn][maxn];

int main(){
    std::scanf("%d%d", &n, &k);
    for(int i = 1, j; i <= n; ++i)
        std::scanf("%d", &j), a.push_back(j), T.push_back(j);
    for(int i = 1, j; i <= k; ++i)
        std::scanf("%d", &j), T.push_back(j);
    T = parity_set(T);
    if((int)T.size() > n || (n - T.size()) & 1){
        std::puts("-1");
        return 0;
    }
    std::sort(a.begin(), a.end());
    std::memset(dp, 0x3f, sizeof dp), dp[0][0] = 0;
    for(int i = 1; i <= n; ++i){
        int lim = std::min<int>(i, T.size());
        for(int j = 1; j <= lim; ++j)
            dp[i][j] = dp[i - 1][j - 1] + std::abs(a[i - 1] - T[j - 1]);
        if(i >= 2)
            for(int j = 0; j <= lim; ++j)
                dp[i][j] = std::min(dp[i][j], dp[i - 2][j] + std::abs(a[i - 1] - a[i - 2]));
    }
    std::printf("%lld\n", dp[n][T.size()]);
    return 0;
}

来源¶

AtCoder Regular Contest 114 D - Moving Pieces on Line

D - Moving Pieces on Line¶

题意¶

解析¶

实现¶

来源¶

评论