P3694 邦邦的大合唱站队

2025-05-26

同样是 @GUAIKATTO 给我推的题目。

题意

有 \(n\) 个数字，均为 \([1, m]\)，我们可以取出一些数字，然后重新安排它们的位置，需要使得最终所有相同的数字都相邻，问最少要排几个数字的位置。

思路

其实 tag 里看到状压dp了，就该完全不看 tag 的。。。因为 M 只有 \(20\)，所以状态总共只有 \(2^{20}\) 种，可以使用状压dp。即为 \(1\) 的位表示已经排好了，那么我们可以在当前状态还没有选择的数字中，选择一种，然后看需要花费多少。

那么显然就是后面 \(cnt_x\) 个数字中不等于 \(x\) 的数字的个数。

其实就是一个很基础的状压DP哈，很快就 AC 了。

// #define YUANSHEN
#if defined(YUANSHEN)
#include "C:/codes/cp_code/template/debug.hpp"
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) 42
#endif

#define rep(N) for(int i = 1; i <= N; i++)

template <typename T1, typename T2>
void cmin(T1& x, const T2& y)
{
    x = x < y ? x : y;
}
template <typename T1, typename T2>
void cmax(T1& x, const T2& y)
{
    x = x > y ? x : y;
}
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using vc = vector<T>;

#define fixset(x) fixed << setprecision(x)
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ALL(x) (x).begin() + 1, (x).end()
constexpr int INF = 1000000000;
constexpr ll LNF = 1000000000000000000LL;

// Date: 2025-05-26
// Time: 10:39:15
int dp[1048576];

void ChatGptDeepSeek()
{
    memset(dp, 0x3f, sizeof dp);
    int n, m;
    cin >> n >> m;
    vi a(n + 1), cnt(m);
    vc<vi> pre(n + 1, vi(m));
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        cnt[--a[i]]++;
        pre[i] = pre[i - 1];
        pre[i][a[i]]++;
    }
    dp[0] = 0;
    for(int i = 0; i < (1 << m); i++){
        int len = 0;
        for(int j = 0; j < m; j++)
            if(i >> j & 1) len += cnt[j];
        for(int j = 0; j < m; j++){
            if((i >> j & 1) == 0){
                dp[i ^ (1 << j)] = min(dp[i ^ (1 << j)], dp[i] + (cnt[j] - (pre[len + cnt[j]][j] - pre[len][j])));
            }
        }
    }
    cout << dp[(1 << m) - 1];
}

int main()
{
#ifndef YUANSHEN
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
#endif
    // cerr << (1 << 20) ;
    int T = 1;
    // cin >> T;
    while (T--)
        ChatGptDeepSeek();
    return 0;
}