牛客国庆集训派对Day2 E数据排序 (状压DP + lowbit/最高位转移)

这种题一般都是按从小到大赋值$c$。我们可以设$dp(S)$为前面已经赋值的最小值。

然后我们就可以枚举剩下元素的子集来加入，这个子集所有元素都是一个值，且大于之前所有的值。

那么我们可以预处理出来前面一个求和，后面的求和也可以预处理。

前面的求和先预处理出一个点对一个集合的，再在DP过程中从小到大去转移集合对集合的。用最高位转移。这样可以免去枚举一个$n$，具体可以看代码中的$p$

知识点：
1、状态设计方法
2、lowbit/最高位转移

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const LL MAXN = 15 + 1;

    LL n, g[MAXN][MAXN], high[(1 << 15) + 1];
    LL val[MAXN][(1 << 15) + 1], gg[(1 << 15) + 1], p[(1 << 15) + 1];
    LL dp[(1 << 15) + 1], st[(1 << 15) + 1], top;

    LL abss(LL x) {return x > 0 ? x : -x;}

    void clean() {
    }
    int solve() {

        clean();
        cin >> n;
        for (LL x, y, i = 1; i <= 2ll * n * (n - 1); ++i) scanf("%lld%lld", &x, &y), ++g[x][y];
        for (LL S = 0; S < (1 << n); ++S) {
            for (LL i = 1; i <= n; ++i) if (S & (1 << (i - 1))) {
                for (LL j = i + 1; j <= n; ++j) if ((S & (1 << (j - 1)))) {
                    gg[S] += abss(g[i][j] - g[j][i]);
                }
            }
        }
        for (LL i = 1; i <= n; ++i) {
            for (LL S = 0; S < (1 << n); ++S) if (!(S & (1 << (i - 1)))) {
                for (LL j = 1; j <= n; ++j) if (S & (1 << (j - 1))) val[i][S] += g[j][i]; // i > j
            }
        }
        for (LL S = 1; S < (1 << n); ++S)
        for (LL i = 1; i <= n; ++i) if (S & (1 << (i - 1))) high[S] = i;

        ms(dp, 0x3f);
        dp[0] = 0;
        for (LL i = 1; i <= n; ++i) dp[1 << (i - 1)] = 0;
        for (LL S = 0; S < (1 << n); ++S) {
            LL C = ((1 << n) - 1) & (~S);
            top = 0;
            for (LL T = C; T; T = (T - 1) & C) st[++top] = T;
            while (top) {
                LL T = st[top--];
                p[T] = p[T ^ (1 << (high[T] - 1))] + val[high[T]][S];
                dp[S ^ T] = min(dp[S ^ T], dp[S] + gg[T] + p[T]);
            }
        }
        printf("%lld\n", dp[(1 << n) - 1]);

        return 0;
    } 
}
int main() {
    flyinthesky::solve();
    return 0;
}