HDU

HDU - 5823

枚举子集， 把一种颜色的一起加进去dp， 感觉3^n的复杂度不知道为啥跑这么快。

可以用fwt优化到(2 ^ n) * n * n

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0)                     ;

using namespace std;

const int N = 3e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = (int)1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);

template<class T, class S> inline void add(T &a, S b) {a += b; if(a >= mod) a -= mod;}
template<class T, class S> inline void sub(T &a, S b) {a -= b; if(a < 0) a += mod;}
template<class T, class S> inline bool chkmax(T &a, S b) {return a < b ? a = b, true : false;}
template<class T, class S> inline bool chkmin(T &a, S b) {return a > b ? a = b, true : false;}

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
bool ok[1 << 18];
char s[18][30];

unsigned int dp[1 << 18];
unsigned int Pow[1 << 18];

int main() {
    for(int i = Pow[0] = 1; i < (1 << 18); i++) {
        Pow[i] = Pow[i - 1] * 233;
    }
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%s", s[i]);
        }
        for(int i = 0; i < (1 << n); i++) {
            ok[i] = true;
        }
        for(int mask = 0; mask < (1 << n); mask++) {
            for(int i = 0; i < n; i++) {
                if(mask >> i & 1) {
                    for(int j = i + 1; j < n; j++) {
                        if(mask >> j & 1) {
                            if(s[i][j] == '1') {
                                ok[mask] = false;
                                i = n;
                                break;
                            }
                        }
                    }
                }
            }
        }
        unsigned int ans = 0;
        dp[0] = 0;
        for(int i = 1; i < (1 << n); i++) {
            dp[i] = n;
            for(int j = i; ; j = (j - 1) & i) {
                if(ok[i ^ j]) chkmin(dp[i], dp[j] + 1);
                if(!j) break;
            }
            ans += dp[i] * Pow[i];
        }
        printf("%u
", ans);
    }
    return 0;
}

/*
*/