状压DP

---

最短Hamilton路径

原题链接

给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

假设有20个点，状态数量（2^20 * 20） * 状态转移(20)的时间复杂度：

2千万 * 20 ≈ 4亿

旅行商问题是一个NPC问题，无多项式级别的算法可以做出来
（P问题是多项式时间复杂度的算法可以做出来，NP问题是不确定能否是用多项式时间解决的问题）

就数量上而言，NP问题远比P问题要多，而NP之中的NPC问题也仅占极少数，所以P、NP、NPC之间的关系可以用下图来表示：

因为NPC问题都能由NP问题归约而来，所以俗话说擒贼先擒王，只要有朝一日，我们能够找到NPC问题的多项式时间算法，就能够解决掉所有的NP问题！但遗憾的是，至今还没有人能够找到可行的方法，很多人认为这些问题是无解的。

首先先暴力枚举一些状态，对于这些路径，我们只关心走过了哪些点和当前停在哪些点上，就比如0123与0213，而并不关心里面点的顺序什么，只需要取这两个路径中的较小值即可

因此用dp分析法：

dp[state][j]表示当前走过的点的集合是state，且当前停在j这个点就可以不重不漏地表示完整个状态空间，

属性是min

转移的复杂度是2^20 * 20 * 20约等于4亿约4秒

转移方程为dp[state][j]=min(dp[state][j],dp[state_k][k]+w[k][j]);
由k点转移到j点是否会使路径变得更短

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=1<<20,M=20;

int n;
int f[N][M],weight[M][M];

//N为当前哪些点被用过，用20位二进制表示每个点的状态，1表示被访问过，0表示没有被访问过
//M当前停在哪些点

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 state=0;state<1<<n;state++)
    {
        for(int j=0;j<n;j++)//先枚举状态
        {
            if(state>>j&1)//如果state集合中第j位是1，也就是到达过这个点
            {
                for(int k=0;k<n;k++)
                {
                    if(state-(1<<j)>>k&1)//state_k==state-(1<<j),为state除掉j之后的集合,且状态里面要包含k
                            f[state][j]=min(f[state][j],f[state-(1<<j)][k]+weight[k][j]);
                }
            }
        }
    }
    
    cout<<f[(1<<n)-1][n-1];
    return 0;
}

---

原题链接

求把N * M的棋盘分割成若干个1*2的的长方形，有多少种方案。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int N=12,M=1<<N;

ll dp[N][M];

int n,m;
vector<int>state[M];//所有能转移到他的合法状态先预处理

bool st[M];//判断某个状态是否合法，当前这一列是否能用1*2小方格填满

int main()
{
    while(cin>>n>>m,n||m)
    {
        //首先预处理
        for(int i=0;i<1<<n;i++)
        {
            //所有连续的0是否有偶数个
            int cnt=0;//表示0的个数
            
            bool is_valid=true;
            
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)//当前这一位是1
                {
                    if(cnt&1)//前面0有奇数个
                    {
                        is_valid=false;//标记为不合法
                        break;
                    }
                    cnt=0;
                }
                else//当前这一位是0
                    cnt++;
            }
            //判断一下最后一段是否是奇数个0
            if(cnt&1)   is_valid=false;
            
            st[i]=is_valid;
        }
        
        
        for(int i=0;i<1<<n;i++)//枚举所有状态
        {
            state[i].clear();
            for(int j=0;j<1<<n;j++)
            {
                if((i&j)==0&&st[i|j])//1.i与j不能在同一行都有一，2.所有填满的位置是合法的
                    state[i].push_back(j);
            }
        }
        memset(dp,0,sizeof dp);
        dp[0][0]=1;//都竖放
        
        for(int i=1;i<=m;i++)
            for(int j=0;j<1<<n;j++)
                for(auto k : state[j])
                    dp[i][j]+=dp[i-1][k];
                    
        cout<<dp[m][0]<<endl;//0~m-1列已经摆放好，且从0~m-1列伸到m列的状态数是0
    }
    
    return 0;
}