# 位元dp

* 用0, 1代表一個物件選或不選的狀態，壓縮成二進位集合，所以可以同時代表多個物件的01的狀態

位元操作
---
* 在k位元新增1：```n | (1<<k)```
* 在k位元刪除1：```n ^ (1<<k)```

c460: 3. 軍隊部署
---
https://zerojudge.tw/ShowProblem?problemid=c460

* 不停的or，也就是一直計算各角色總共覆蓋到的技能，把每種覆蓋的組合壓縮成二進位存在dp

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

LL dp[10]={0}, ft[10]={0}, sec[10]={0}, thd[10]={0}, dp2[10]={0};

int dec(int a, int b, int c){
    int res=0;
    if(a) res=1;
    if(b) res|=1<<1;
    if(c) res|=1<<2;
    return res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, a, x;
    cin>>n;
    rep(i,0,n){
        cin>>a;
        int q,w,e;
        cin>>q>>w>>e;
        if(a==1) ft[dec(q,w,e)]+=1;
        else if(a==2) sec[dec(q,w,e)]+=1;
        else thd[dec(q,w,e)]+=1;
    }
    // 2
    rep(i,0,8){
        rep(j,0,8){
            dp[i|j]+=sec[i]*ft[j];
        }
    }
    // 3;
    rep(i,0,8){
        rep(j,0,8){
            dp2[i|j]+=thd[i]*dp[j];
        }
    }
    cout<<dp2[7]<<NL;
}

traveling salesman problem
---
https://judge.tcirc.tw/ShowProblem?problemid=d089

* 設家為m
* ```dp[i][a]```: 從i開始到m經過所有**二進位a中為1的位置**一次的最短路徑
* 初始化所有點到m的距離（包括m到其他一個點再回到m的距離）
* 生成所有二進位組合a（從3個開始），並算出所有起點經過a集合中的最短路徑（枚舉下一個點做轉移）
* 轉移：```dp[i][a] = min(dp[i][a], dis[i][j]+dp[j][a & ~(1<<i)])```
* i為起點，只能是a中為1的點
* a為集合
* j是i下一個的點，枚舉j，要為a中為1的點
* ```dis[i][j]+dp[j][a & ~(1<<i)]```為i到j距離加上從j開始但不經過i的最短路徑（用bitmask）

* 要特別計算i(起點)=m的值，在同個集合a計算完所有i!=m後，計算從i=m開始經過集合所有點（m為終點一樣要經過）的值
* 轉移：```dp[i][a] = min(dp[i][a], dis[i][j]+dp[j][a])```

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

LL dp[20][300000]={0};
int dis[20][20]; //i: start point, j:subset
vector<int> subset;
int n,m;

void combination(int k, int set, int at){
    rep(i,at,n){
        set|=1<<i;
        if(k==1) subset.EB(set);
        else combination(k-1, set, i+1);
        set&=~(1<<i); // unset 1 in pos i
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    rep(i,0,n)
        rep(j,0,n)
            cin>>dis[i][j];

    // initialize every start point
    for(int i=0;i<n;++i){
        if(i==m) continue;
        dp[i][1<<m | 1<<i]=dis[i][m];
    }
    // starting from home
    for(int i=0;i<n;++i){
        if(i==m) continue;
        dp[m][1<<m | 1<<i]=dis[i][m]*2;
    }

    // bitset with k bits of 1
    for(int k=3;k<=n;++k){
        subset.clear();
        combination(k, 0, 0);
        for(auto a:subset){
            if(!(a & 1<<m)) continue;// if bitset doesn't contain home exclude it
            for(int i=0;i<n;++i){
                if(i==m || !(a & 1<<i)) continue;
                dp[i][a]=INT_MAX;
                for(int next=0;next<n;++next){
                    if(i==next || !(a & 1<<next)) continue;
                    dp[i][a]=min(dp[i][a], dis[i][next]+dp[next][a & ~(1<<i)]);
                }
            }
            // from home
            dp[m][a]=INT_MAX;
            for(int next=0;next<n;++next){
                if(m==next || !(a & 1<<next)) continue;
                dp[m][a]=min(dp[m][a], dis[m][next]+dp[next][a]);
            }
        }
    }

    int all=0;
    for(int i=0;i<n;++i) all|=1<<i;
    cout<<dp[m][all]<<NL;
}