状压 DP

## [P1171 售货员的难题](https://www.luogu.com.cn/problem/P1171)

我们如果要存储 $20$ 个点有没有到过，需要开 $20$ 维数组。

但是这样存储太麻烦了，我们可以考虑存储存储一个二进制数，其第 $i$ 位为 $1$ 表示到过，否则表示没到过。

最后的答案为到达所有点后随便选一个点回到 $1$ 的总路程的最小值，即 $\max(dp_{2^{n-1},i})+dis_{i,1}$。

时间复杂度 $O(2^n\times n)$，状压 DP 一般处理 $n\le 20$ 时的情形。

```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
int w[21][21];
int dp[(1<<20)][21]; 
signed main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>w[i][j];
		}
	}memset(dp,0x3f,sizeof dp);
	dp[1][0]=0;
	for(int i=1;i<(1<<n);i+=2){
		for(int j=0;j<n;j++){
			if((i>>j)&1==0)continue;
			for(int k=0;k<n;k++){
				if((i>>k)&1==0)continue;
				dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+w[k][j]);
			}
		}
	}int ans=1e9;
	for(int i=1;i<n;i++){
		ans=min(ans,dp[(1<<n)-1][i]+w[i][0]);
	}
	cout<<ans;
	return 0;
}
```

其中有一些位运算的技巧：
1. `(i>>j)&1` 表示获取数字 $i$ 从右往左数的第 $j$ 位（最低位为 $0$）。

2. `i^(1<<j)` 表示表示将数字 $i$ 从右往左数的第 $j$ 位（最低位为 $0$）翻转。

3. `(1<<n)-1` 表示二进制下拥有 $n$ 个 $1$。

## [P2704 [NOI2001] 炮兵阵地](https://www.luogu.com.cn/problem/P2704)

此题的重点在于如何判断一行与相邻两行放置状态是否合法。

### 1.判断是否放置的地方为平原

我们假设山地是 $0$，平原是 $1$，且当前行的地形为 $y$，假设当前遍历到的状态为 $x$，则当且仅当 $x\,\mathrm{and}\,y=x$，因为：
- 若放置在一位的点为平原，由于 $1\,\mathrm{and}\,1=1$，不会对 $x$ 的这一位造成影响。

- 若放置在一位的点为山地，由于 $1\,\mathrm{and}\,0=0$，会对 $x$ 的这一位造成影响。

- $0\,\mathrm{and}\,\text{任何数}=0$，所以 $x$ 中不放置的为不会有任何影响。

### 2.判断一行中有没有左右两位相邻

我们使用 $\mathrm{lsh}$ 表示左移。

当 $(x\,\mathrm{lsh}\,1)\,\mathrm{and}\,x=0$ 且 $(x\,\mathrm{lsh}\,2)\,\mathrm{and}\,x=0$ 时，则没有相邻。

为什么？我们以 $(x\,\mathrm{lsh}\,1)\,\mathrm{and}\,x=0$ 为例，则相邻的两个 $1$ 中，后面的会移到前面去，相与后会出现 $1$，若没有相邻的两个 $1$，就不会出现任何 $1$。

$(x\,\mathrm{lsh}\,2)\,\mathrm{and}\,x=0$ 同理。

### 3.判断一行中有没有上下两位相邻

若当前行为 $x$，上面那行为 $y$，上上行为 $z$，则 $x\,\mathrm{and}\,y=0$，$x\,\mathrm{and}\,z=0$，$y\,\mathrm{and}\,z=0$，则合法。

这个非常好证：若满足该条件，当且仅当同一位未出现两个 $1$，随便取两个数判断是否同一位有两个 $1$ 就行了。

给出代码：

```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m;
int dp[101][1<<10][1<<10];
int a[101];
int count(int x){
	int ans=0;
	while(x>0){
		ans+=(x%2);
		x/=2;
	}return ans;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=0;j<m;j++){
			char c;
			cin>>c;
			if(c=='P')a[i]|=(1<<j);
		}//cout<<a[i]<<"\n";
	}
	dp[0][0][0]=0;
	for(int j=0;j<(1<<m);j++){
		if(((j<<1)&j)==0&&((j<<2)&j)==0&&(j&a[1])==j){
			dp[1][j][0]=count(j);
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=0;j<(1<<m);j++){
			int x=count(j);
			if(((j<<1)&j)!=0||((j<<2)&j)!=0||(j&a[i])!=j){
				continue;
			}for(int k=0;k<(1<<m);k++){
				if((k&j)!=0){
					continue;
				}for(int l=0;l<(1<<m);l++){
					if((j&l)!=0){
						continue;
					}dp[i][j][k]=max(dp[i][j][k],dp[i-1][k][l]+x);
				}
			}
		}
	}int ans=-1e9;
	for(int i=0;i<(1<<m);i++){
		for(int j=0;j<(1<<m);j++){
			ans=max(ans,dp[n][i][j]);
		}
	}cout<<ans;
	return 0;
}
```

但是这个方法太慢了。

容易发现满足第二个条件的数很少，只有 $50$ 个，可以去预处理。

然后这么计算即可。

```cpp
#include <bits/stdc++.h>
using namespace std;
int n,m;
int dp[105][65][65];
int a[105];
int id[105],cnt;
int count(int x){
	int ans=0;
	while(x>0){
		ans+=(x%2);
		x/=2;
	}return ans;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=0;j<m;j++){
			char c;
			cin>>c;
			if(c=='P')a[i]|=(1<<j);
		}//cout<<a[i]<<"\n";
	}
	for(int j=0;j<(1<<m);j++){
		if(((j<<1)&j)==0&&((j<<2)&j)==0){
			id[++cnt]=j;
		}
	}
	for(int i=1;i<=n;i++){
		for(int jj=1;jj<=cnt;jj++){
			int j=id[jj];
			int x=count(j);
			if(((j<<1)&j)!=0||((j<<2)&j)!=0||(j&a[i])!=j){
				continue;
			}for(int kk=1;kk<=cnt;kk++){
				int k=id[kk];
				if((k&j)!=0){
					continue;
				}for(int ll=1;ll<=cnt;ll++){
					int l=id[ll];
					if((j&l)!=0){
						continue;
					}dp[i][jj][kk]=max(dp[i][jj][kk],dp[i-1][kk][ll]+x);
				}
			}
		}
	}int ans=-1e9;
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=cnt;j++){
			ans=max(ans,dp[n][i][j]);
		}
	}cout<<ans;
	return 0;
}
```

## [SP1700 TRSTAGE - Traveling by Stagecoach](https://www.luogu.com.cn/problem/SP1700)

这题是无向图，没有拓扑序，需要寻找子问题。

由于票只能用一次，子问题自然就是票。

我们定义 $dp_{i,j}$ 表示用票状态为 $i$，当前到的点为 $j$ 时的最小。

我们还需枚举当前用了哪个票，有哪个点转移过来，状态转移方程为：`dp[i][j]=min(dp[i][j],dp[i^(1<<k)][v]+dis[j][v]/c[k]);`。

给出代码：

```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p,a,b;
struct kkk{
	int x;
	double w;
};
vector<kkk> g[35];
int c[10];
double dp[1<<8][35];
void solve(){
	for(int i=1;i<=m;i++)g[i].clear();
	for(int i=0;i<n;i++)cin>>c[i];
	for(int i=1;i<=p;i++){
		int u,v;
		double w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}for(int i=0;i<(1<<n);i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=1e9;	
		}
	}
	dp[0][a]=0;
	for(int i=0;i<(1<<n);i++){
		for(int k=0;k<n;k++){
			if(i&(1<<k)==0)continue;
			for(int j=1;j<=m;j++){
				for(int l=0;l<g[j].size();l++){
					int v=g[j][l].x,w=g[j][l].w;
					dp[i][j]=min(dp[i][j],dp[i^(1<<k)][v]+w*1.0/c[k]);
				}
			}
		}
	}double ans=1e9;
	for(int i=0;i<(1<<n);i++){
		ans=min(ans,dp[i][b]);
	}if(ans==1e9)cout<<"Impossible\n";
	else cout<<ans<<"\n";
}
signed main(){
	while(cin>>n>>m>>p>>a>>b){
		if(n==0&&m==0&&p==0&&a==0&&b==0)break;
		solve();
	}
	return 0;
} 
```