状压DP - 洛谷保存站

# 状态压缩
用一个**整数**来记录状态：

整数的每个二进制位对应一个物品，0未选，1已选

# 例题
## [传球游戏(模板)](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=J)
通过题目得知每个人传给其他人的消耗都**不一样**，所以使用**状态压缩DP**

使用f[i][j]数组，表示在i状态下（i的**二进制**每一位对应一个人**是否**接到球）且**当前拿球的人**是j的总共消耗

### 先进行初始化
```cpp
  for(long long i=0;i<1<<n;i++)
	{
		for(long long j=0;j<n;j++)
		{
			f[i][j]=1e18;
		}
	}
	for(long long i=0;i<n;i++)
	{
		f[1<<i][i]=0;//每一个人都可以是开始那个
	}
```
### DP

```cpp
for(long long S=2;S<1<<n;S++)
	{
		for(long long i=0;i<n;i++)
		{
			if(S>>i&1)
			{
				for(long long j=0;j<n;j++)
				{
					if(i!=j&&(S>>j&1))
					{
						f[S][i]=min(f[S][i],f[S^1<<i][j]+c[j][i]);
					}
				}
			}
		}
	}
```
### 最后的答案为ans=min(ans,f[(1<<n)-1][i])(i枚举每一个球)

---

## [过桥](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=K)
相较于前一题每次更新不再只是一个数字，而是一个**集合**

使用**一维数组**记录状态即可

先**初始化每种状态所用的时间**，更新时枚举i的子序列，看f[i]是否能从f[i子序列]更新过来

### 初始化
```cpp
	for(long long i=0;i<tot;i++)
	{
		for(long long j=0;j<n;j++)
		{
			if(i>>j&1)
			{
				hea_s[i]+=hea[j];
				tim_s[i]=max(tim_s[i],tim[j]);
			}
		}
	}
```
### DP
```cpp
	for(long long s=1;s<tot;s++)
	{
		f[s]=1e18;
		for(long long s2=s;s2;s2=s&(s2-1))
		{
			if(hea_s[s2]<=w)
			{
				long long s1=s^s2;
				f[s]=min(f[s],tim_s[s2]+f[s1]);
			}
		}
	}
```

---

## [校长的烦恼](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=M)
难点在于每个岗位有**三种情况=**0，=1或>=2

f[i][j]表示状态i的岗位有大于等于2的老师，状态j的岗位有大于等于1的老师

### 先初始化不得不用到的老师 
```cpp
	for(long long i=1,S1=0,S2=0;i<=n;i++)
	{
		S2=S2|(S1&have[i].sj);
		S1=S1|have[i].sj;
		f[S1][S2]=ans;

}
```
对于每个老师，枚举f[i][j]看是否能通过该老师更新到这个状态
### DP

```cpp
	for(long long s=1;s<tot;s++)
	{
		f[s]=1e18;
		for(long long s2=s;s2;s2=s&(s2-1))
		{
			if(hea_s[s2]<=w)
			{
				long long s1=s^s2;
				f[s]=min(f[s],tim_s[s2]+f[s1]);
			}
		}
	}
```

---

## [送外卖](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=N)
和传球差不多，只是**用订单作为状态而非城市**，加个folyd即可

---

## [【状压】玉米地](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=P)
枚举**每一行**，再枚举每个状态，先确保它是输入中**可以存在**的状态，再看**同一行是否有相邻**，再枚举上一行的状态，确保**上一行与这一行不冲突**后再更新
```cpp
	for(long long i=1;i<=m+1;i++)
	{
		for(long long S=0;S<(1<<n);S++)
		{
			if(((Can[i]&S)==S)&&((S&(S<<1))==0))
			{
				for(long long T=0;T<(1<<n);T++)
				{
					if((((Can[i-1]&(~S))&T)==T))
					{

f[i][S]=(f[i][S]+f[i-1][T])%100000000;
					}
				}
			}
		}
	}
```

---

## [【NOI2001 Day2 T2】炮兵阵地](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=S)
与玉米田不同的是影响范围从前后左右1格到了2格

开3维数组f[i][j][k],表示第i行状态为j上一行状态为k最大炮兵部队数量

先初始化每种状态放的炮兵数量
```cpp
	for(long long i=0;i<(1<<n);i++)
	{
		for(long long j=0;j<=11;j++)
		{
			if((i&(1<<j))!=0)H[i]++;
		}
	}
```

直接三维数组会炸掉，因为**左右2格不相邻的条件**已经让许多情况不存在，所以只用存**存在情况**即可

```cpp
	for(long long i=2;i<=m+1;i++)
	{
		cnt[i]=0;
		for(long long j=0;j<(1<<n);j++)
		{
			if(((j&(j<<1))==0)&&((j&(j<<2))==0))Map[i][++cnt[i]]=j;
		}
	}
```
DP

```cpp
	for(long long i=2;i<=m+1;i++)
	{
		for(long long s=1;s<=cnt[i];s++)
		{
			long long S=Map[i][s];
			if((S&Can[i])!=S)continue;
			for(long long t=1;t<=cnt[i-1];t++)
			{
				long long T=Map[i-1][t];
				if((T&Can[i-1]&(~S))!=T)continue;
				for(long long u=1;u<=cnt[i-2];u++)
				{
					long long U=Map[i-2][u];
					if((U&Can[i-2]&(~S)&(~T))!=U)continue;
					f[i][s][t]=max(f[i][s][t],f[i-1][t][u]+H[S]);
					ans=max(f[i][s][t],ans);
				}
			}
		}
	}
```

正在渲染内容...