DP - 洛谷保存站

## 状压 DP
状压 dp，说白了就是把dp状态转移的一些状态通过二进制压缩进一个集合里（不然十多维的数组写着不累吗）。如表示第 $a_1,a_2,a_3…a_i$ 这几个节点去过没有，可以用 $f_{a_1,a_2,a_3,…,a_i}=1$ 表示，也可以把这些节点变成一个二进制集合，即 $f_{2^{a_1-1}+2^{a_2-1}+2^{a_3-1}+…+2^{a_i-1}}=1$

### 题目：
目前题目有两种，一种是旅行商问题，就是在一个图上，问从一个点出发，不重复的遍历每个点各一次，最后回到起点，求最短距离。还有一种题，如 [acwing 1064. 小国王](https://www.acwing.com/problem/content/1066/) 这道题，在一个二维平面内，在满足一些条件（如不相邻）的情况下，求如最多能放多少个，有多少种方案这类问题。当然，也有在一个序列上的.

### [J 传球游戏](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=J)
第一类的板子题，同时，注意 dp 也可以用 dfs 实现。

```cpp
int dfs(int x,int s,int sum){//s表示当前走过了哪些点，x表示在哪个点
	if(f[x][s]!=inf) return sum+f[x][s];//记忆化搜索也是dp
	for(int i=1;i<=n;i++){
		if(s&(1<<i-1)) continue;//走到过了
		f[x][s]=min(f[x][s],dfs(i,s|(1<<i-1),a[x][i]));//更新数组
	}
	return sum+f[x][s];
}
```

### [P1433 吃奶酪](https://www.luogu.com.cn/problem/P1433)
没啥区别，只是注意要提前处理距离，这里用递推来dp
#### 处理距离
```cpp
double ju(double x1,double y1,double x2,double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
…
for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			a[i][j]=ju(b[i].x,b[i].y,b[j].x,b[j].y);
		}
}
```
#### 转移
```cpp
for(int i=1;i<1<<n;i++){
		for(int j=1;j<=n;j++){
			if((i&(1<<j-1))==0) continue;
			for(int k=1;k<=n;k++){
				if(j==k||((i&(1<<k-1))==0)) continue;
				if(f[j][i]>f[k][i^(1<<j-1)]+a[j][k]){
					f[j][i]=f[k][i^(1<<j-1)]+a[j][k];
				}
			}
		}
	}
```
### [P【状压】玉米地](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=P)
第二类题，主要就是判断一下相邻
```cpp
bool check(int x){//左右相邻
	if((x&(x>>1))==0) return 1;
	return 0;
}
for(int i=0;i<1<<m;i++){
		for(int j=0;j<1<<m;j++){
	//		cout<<i<<"- "<<(j&(j>>1))<<endl;
		//	cout<<i<<" "<<check(i)<<":"<<(i&j)<<endl;
			if(((i&j)==0)/*上下相邻*/&&(check(i)==1)&&(check(j)==1)){
			//	cout<<i<<" "<<j<<endl;
				v[i].push_back(j);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<1<<m;j++){
			if((j&a[i])==0){
				for(int k=0;k<v[j].size();k++){
					if((a[i-1]&v[j][k])==0){
						f[i][j]+=f[i-1][v[j][k]];
						f[i][j]%=mod;
					}
				}
				if(i==n) ans=(ans+f[i][j])%mod;
			}
		}
	}
```

正在渲染内容...