题解 P1171 【售货员的难题】

· · 题解

写这份题解，是想要作为 状压 + dp的入门指南

一想起我刚学状压的时候，怎一个苦字了得

为了防止有人步入我的后尘，所以这篇题解主要是为了扫盲，各位吃瓜的大佬可以走了

一，二进制运算

[洛谷日报第79期]二进制与位运算

这个实在太重要了，先把二进制运算搞懂了，再来搞状压

二，状压是什么？

众所周知，OI是一个搞数学的学课，所谓状压，就是把一个状态表示成一个集合，再把集合表示成二进制数

总的来说就有这样一个过程

状态 - > 集合 - > 二进制

在进入具体操作之前，我想先和各位讨论一下，为什么要把集合转成二进制数呢？

二进制，这是一个美妙的进制数，0/1，表达了 有 或者 没有

而使用两进制数来描述集合，意味着集合的这个元素 有 或者 没有

比如集合S，有4个元素

1111 这个两进制数就能够表达集合 s

那如果要表达集合s，去除第二个元素，这样的子集怎么表示呢？

1011，而去除掉第二个 和 第三个元素的二进制数， 是1001

推而广之，如果全集共有 N 个元素，

去除掉 第a1, 第a2， 第a3... 第an号元素的子集，

就是把 N个1构成的两进制数的所有的{an}位上的1，变成0

向一个集合 s 中加入第 i 号元素，

就是把两进制数的第 i 位从 0 变为 1

向一个集合 s 中删除入第 i 号元素，

就是把两进制数的第 i 位从 1 变为 0

下面是整理的一些两进制上的常用操作(我刚刚给你们的链接上有详细的解析，这里只是总集)

//集合 s 代表当前集合
//右数 k 位二进制数 0/1 代表 第 k 号元素 不在集合 / 在集合 里 

//必备操作1： 
//将第k个元素加入集合
s | (1 << (k - 1));

//必备操作2：
//将第k个元素从集合中删除
s & (~ (1 << (k - 1)) );

//必备操作3：
//1)如果第k个元素在 集合s里， 删除它
//2)如果不在，把它加入集合s
//可以想象成一盏灯的开关:
//按下开关， 明 -> 暗， 暗 -> 明 
s ^ (1 << (k - 1));

//必备操作4:
//判断元素k 是否在集合s里
//在：返回1，不在：返回0 
(s >> (k - 2)) & 1 == 1

三，怎么建模？

step1 : 怎么用集合描述状态？

以这道题目为例，什么是状态？

一个城市是否已经被走过了可以作为状态，这样就可以把 走过的城市作为一个集合，表示成二进制数

step2 : 怎么dp？

这个....枚举就好。

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 450;

int rd(){
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-'){f = - 1;} c = getchar();}
    while(c >= '0' && c <= '9'){x = x*10 + c - '0'; c = getchar();}
    return x * f; 
}

int N, c[maxn][maxn], f[1 << 20][20];

int dp(){
    //1 << N代表全集
    memset(f,0x3f3f3f,sizeof(f));
    f[(1 << N) - 1][0] = 0;
    for(int s = (1 << N) - 2; s >= 0 ; s--){
        for(int v = 0; v < N ; v++){ 
            //枚举当前集合，售货员处在的位置
            for(int u = 0; u < N; u++){
                if( (s >> u) & 1)continue;//说明已经到过u这个节点了 

                f[s][v] = min(f[s][v], f[s|(1 << u)][u] + c[v][u]);

            } 
        }
    }
}

int main(){
    N = rd();
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < N; j++){
            c[i][j] = rd();
        }
    }
    dp();
    cout<<dp[0][0];
}