Armchairs

Created by LXC on Thu Sep 21 09:38:53 2023

https://codeforces.com/problemset/problem/1525/D

ranting: 1800

tag: dp, flows, graph matchings, greedy

problem

给出一个长度为n的01数组，1的个数不超过0的个数。

我们可以将1与某个0交换，代价是两者之间的距离。

现在需要通过交换操作，让所有原本是1的位置都变为0，并求最小代价。

solution

假设有k个1，我们给它们编上号，那么通过若干次操作后，这k个1相对之前的编号是不变的。

如果编号变化了，说明存在交错移动，但是交错移动不会更优，甚至更劣。

既然相对位置不变化。那么可以类比最长公共子序列，

设第i个1的位置为$p_i$，第i个0的位置为$q_i$

设$f_{i,j}$为前i个1与前j个0的最小移动代价，($i\le j$)。

初始化

$f_{-1,j} = 0$

$f_{i,j}=INF, i\ge0$

$f_{i,j} = min(f_{i, j-1}, f_{i-1, j-1}+|p_j-q_i|)$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define MOD 998244353
#define INF 0x3f3f3f3f
using namespace std;


void sol() {
    int n;
    cin >> n;
    vector<int> p, q;
    for (int i=0; i<n; i++) {
        int x; cin >> x;
        if (x) p.push_back(i);
        else q.push_back(i);
    }
    int psz= p.size(), qsz = q.size();
    vector<vector<int>> f(psz, vector<int>(qsz, -1));
    // f[i][j] = min(f[i][j-1], f[i-1][j-1]+abs(p[i]-q[j]));
    auto dfs = [&](auto self, int i, int j) {
        if (i < 0) return 0;
        if (j < 0) return INF;
        if (f[i][j] != -1) return f[i][j];
        f[i][j] = INF;
        return f[i][j] = min(self(self, i, j-1), self(self, i-1, j-1) + abs(p[i]-q[j]));
    };
    cout << dfs(dfs, psz-1, qsz-1) << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}