状压 DP - 洛谷保存站

## Part 1.基础部分
这种题目最显著的特征：dp 不知道开几维，数据范围很小，这种题十有八九是状压 DP。而状态压缩即为用一个数的二进制去记录这个状态，因此数组需要开 $2^n$。

## Part 2.模版

```cpp
//前面全部初始化为很大的数，每种状态的第一种情况为0
//f[S][i]：S集合中的前i-1个已经处理过，且当前处理到i的最小总代价
//计算f[S][i]时，枚举状态从i转移到j，S二进制的2^j位必须是1，f[S][i]=f[S - 2^i][j]+cost[j][i]
//时间复杂度：O(n^2*2^n)
for(int s=2;s<1<<n;s++){
		for(int i=0;i<n;i++){
			if(s>>i&1){
				for(int j=0;j<n;j++){
					if(i!=j&&(s>>j&1)){
						f[s][i]=min(f[s][i],f[s^1<<i][j]+cost[j][i]);
					}
				}
			}
		}
	}
	for(int i=0;i<n;i++)
		ans=min(ans,f[(1<<n)-1][i]);
```
## Part 3.例题
[K-过桥](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=K)

与护卫队很像，但是没有顺序要求，处理每一个子集可以用位运算，单独记录每一组的最慢时间即可。时间复杂度：$O(3^n$。

```cpp
    //f[1<<i]=a[1<<i];
	for(int s=1;s<1<<n;s++){
		if(s&s-1){
			a[s]=max(a[s&s-1],a[s&-s]);
			b[s]=b[s&s-1]+b[s&-s];
			if(b[s]<=k)f[s]=a[s];
			else{
				f[s]=999999999;
				for(int t=s-1&s;t;t=t-1&s){
					if(b[t]<=k&&f[s]>f[s^t]+a[t]){
						f[s]=f[s^t]+a[t];
					}
				}
			}
		}
	}
```

[M-校长的烦恼](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=M)

难点在于字符串的输入 ```getline```，弄完之后省下的就是普通 DP。

```cpp
//输入处理，两段的差不多
//因为在职教师是必选的，那么可以提前把他们处理出来
//把他们可以教的科目作为初始状态，花费的费用作为初始消耗
//还没选的老师后面 DP
        string x;	
		getline(cin,x);
		int len=x.size();
		for(int j=0;j<len;j++){
			if(x[j]!=' '){
				int t=x[j]-'0';
				s2=s2|(s1&(1<<t-1));
				s1=s1|(1<<t-1);
			}
		}
```

```cpp
//DP 部分
for(int i=1;i<=n;i++){
		for(int j=S;j>=0;j--){
			for(int k=S;k>=0;k--){
				int s11=j|w[i];
				int s22=k|(j&w[i]);
				f[s11][s22]=min(f[s11][s22],f[j][k]+money[i]);
			}
		}
	}
```

[P-玉米地](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=P)

这个题主要是需要根据上一行来处理当前这一行，[S-炮兵阵地](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=S)和这个题一样，不同的只是要根据前面两行来处理，上一行的直接前缀和初始化就行，其他的就是模版。

```cpp
for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			sum[i]=(sum[i]<<1)+a[i][j];
		}
	}
	for(int i=0;i<(1<<m);i++){
		if(!(i&(i>>1))&&!(i&(i<<1))){
			g[i]=1;
			if((i&sum[1])==i)f[1][i]=1;
		}
	}
```

正在渲染内容...