[数据结构与算法]状态DP1

初步认知，有些东西需要集合来表示但是不太方便

比如说00010001000100001 又1的地方就代表这个数在这个集合中存在，于是乎我们就可以用一个数字表示一个集合了。

例题

旅行商问题

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20, M = 1<<20;
int n;
int f[M][N] , weight[N][N];
int main() {
    cin>>n;
    for (int i=0;i<n;i++) {
        for (int j=0; j<n ;j++) {
            cin>>weight[i][j];
        }
    }
    memset(f, 0x3f,sizeof(f));
    f[1][0] = 0;
    for (int i= 0 ;i< 1<<n ; i++) {
        for (int j=0; j<n; j++) {
            if (i >> j & 1) {
                for (int k=0; k<n ;k++) {
                    if (i-(1<<j)>>k &1 ) {
                        f[i][j] = min(f[i][j], f[i-(1<<j)][k] + weight[k][j]);
                    }
                }
            }
        }
    }    
    cout<<f[(1<<n) - 1][n-1]<<endl;
    return 0;
}