最短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;
}
