最小点覆盖问题

o-Sakurajimamai-o / 2024-09-20 / 原文

E. Algebra Flash
做这道题的时候新学的算法, 叫做最小点覆盖.
令 $c_i$ 为在 $i$ 位置的颜色
首先了解题意, 由于我们只能跨 $1$ ~ $2$步, 故此时如果有 $c_i = c_{i+1}$, 则 $c_i$ 这个颜色是必选的, 若两者不相等, 也必须从两者里面选择出一个来, 那么我们可以给相邻的两点连上一条边, 意味着两个点必须有一个点被选择, 这样就转化成: 第 $1$ 个点和第 $n$ 个点必选, 其余相邻的点必选一个, 那么就可以转化成最小点覆盖问题, 我们可以把 $m$ 个点对半分, 然后枚举出前 $\frac{m}{2}$ 个点的状态, 然后再和剩下的点进行合并.

在枚举过程中, 会出现状态某两个点没有选择, 而我们必须要在这两个点中选择一个点, 所以我们此时的情况是无解的, 直接设置成无穷大即可
需要倒着枚举状态, 因为即使出现无解的情况, 我们也要对其进行更新, 也就是符合情况的最小的超集, 例如存在两个点没有选择, 而这两点必须选择一点, 那么我们首先要把这个状态设置成无穷大, 然后去枚举所有没有选择的点, 对他的超集, 也就是符合条件的进行更新, 这样做是为了在合并的时候, 只要后半段有解, 前半段即使无解, 由于我们枚举了超集, 再加上某个点使得这个状态最小, 从而合并
时间复杂度$O(2^{\frac{m}{2}} * (\frac{m}{2})^2)$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18, mod = 1e9 + 7;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n, m; cin >> n >> m;
   
    vector<int> c(n + 1), cost(m + 1);
    for(int i = 1; i <= n; i++) cin >> c[i];
    for(int i = 1; i <= m; i++) cin >> cost[i];

    vector<vector<bool>> a(m + 1, vector<bool> (m + 1));    
    for(int i = 1; i <= n; i++){
        if(i > 1) a[c[i]][c[i - 1]] = true;
        if(i < n) a[c[i]][c[i + 1]] = true;
    }
    a[c[1]][c[1]] = a[c[n]][c[n]] = true;

    int z1 = m / 2, z2 = m - z1;
    vector<int> dp(1LL << (z1 + 1));
    for(int i = (1LL << z1) - 1; i >= 0; i--){ // O(2 ^ (m / 2) * (m / 2) * (m / 2))
        bool ok = true;
        
        for(int j = 1; j <= z1; j++){
            if((i >> (j - 1) & 1) == 0){
                for(int k = 1; k <= z1; k++){
                    if((i >> (k - 1) & 1) == 0 && a[j][k]){
                        ok = false;
                    }
                }
            }
        }

        if(ok){
            for(int j = 1; j <= z1; j++){
                if((i >> (j - 1) & 1)){
                    dp[i] += cost[j];
                }
            }
        } else{
            dp[i] = INF;
            for(int j = 1; j <= z1; j++){
                if((i >> (j - 1) & 1) == 0){
                    dp[i] = min(dp[i], dp[i ^ (1 << (j - 1))]);
                }
            }
        }

    }

    int res = INF;    
    for(int i = 0; i <= (1LL << z2) - 1; i++){
        bool ok = true;

        for(int j = 1; j <= z2; j++){
            if((i >> (j - 1) & 1) == 0){
                for(int k = 1; k <= z2; k++){
                    if((i >> (k - 1) & 1) == 0 && a[z1 + j][z1 + k]){
                        ok = false;
                    }
                }
            }
        } 

        if(!ok) continue;

        int cur = 0, should = 0;
        for(int j = 1; j <= z2; j++){
            if((i >> (j - 1) & 1)){
                cur += cost[z1 + j];
            } else{
                for(int k = 1; k <= z1; k++){
                    if(a[k][j + z1]){
                        should |= (1LL << (k - 1));                        
                    }
                }
            }
        }
        
        res = min(res, cur + dp[should]);

    }

    cout << res << '\n';

    return 0;
}