浅谈一类dp问题----状压dp
___new2zy___
2018-09-28 07:07:42
## 浅谈一类dp问题----状压dp
### ----谨以此篇来纪念我可怜的状压水准
### 撞鸭？状压！(不定期更新)
由于要NOIp复赛了。。。发现自己状压的还很菜
于是乎昨天找了几道典型的例题来刷一刷
发现状压这东西很好玩，涉及了很多优美~~（玄学+毒瘤）~~的位运算
结果就是看半天题之后有了思路结果不会实现QAQ。。。
毕竟。。。窝的位运算学的还是很差的
不多说了，直接写正文好了~
=================================================================
#### 令人憧憬~~（发指）~~的撞鸭（状压）
那么，什么是状压呢？
听起来高大上，其实没什么
下面讲一讲我自己的理解吧（应该有专业术语的，可是我懒，不想度娘）
**状压，即状态压缩的简称，在数据范围较小的情况下，将每个物品或者东西选与不选的状态“压”成一个整数的方法**
通常采用二进制状压法，（对于**二进制状压**）即对于一个我们“压”成的状态，这个整数在二进制下中的1表示某个物品已选，而0代表某个物品未选
这样我们就可以通过枚举这些“压”成的整数来达到枚举所有的物品选与不选的总情况，通常我们称这些情况叫做子集，对于这个状态整数，通常设为s
（对于二进制状压）通过二进制下的位运算来达到判断某个物品选与不选的情况，再通过这个状态来进行一些其他的扩展，能简化我们对于问题的求解方式
而**状压dp正是用到了这一点，通过一个状态来表示整体情况，对于这个情况进行一些最优化操作，最终达到求得全局最优解的目的**
然而还有其他的状压方法，例如**三进制状压**法等等，本人在此就不再赘述
~~（其实是太菜不会讲，应该把机房某dalao拉过来讲一下的）~~
然而对于状压dp，本质上是与dp无异的
说白了，**状压dp，没有改变dp本质的优化方法，阶段还是要照分，状态还是老样子，决策依旧要做，转移方程还是得列，最优还是最优，无后性还是无后性**，所以它还是比较好理解的。
其实我觉得，状压dp可以理解为最暴力的dp，因为它需要遍历每个状态，所以在大多数题目中，会出现2^n的状态，所以最明显的标志就是数据不能太大(大约是$n<=16$)
遍历所有状态的正确姿势就是用二进制的位运算来遍历
对于一个二进制$01$串，$1$表示使用，$0$表示未使用，我们可以把所有的状态投射到很多二进制的数上（类似于hash的思想）
这大概就是状压dp的精髓了吧！
状压dp需要用到一些~~（很多）~~位运算的知识，下面给出一张图说明
~~显然是网上找的QAQ~~
是不是感觉有上面的话有点熟悉？
~~（我是不会告诉你这是我从 [这里](https://www.luogu.org/blog/new2zy/solution-p3959) 搬过来的233）~~
那么下面给出一些昨天做过的状压例题结合说明一下
=================================================================
### ex1:luogu p1896 互不侵犯
题目传送门：
https://www.luogu.org/problemnew/show/P1896
很久以前就听说这题是个状压$dp$，但是总也不敢写$QWQ$
~~（貌似这已经是个状压$dp$的入门题了233）~~
咳咳。。。还是说正经的
题目很明确，一个国王只能攻击它相邻的$8$个格子（$8$联通）
那么如果再次简化，可以发现其实是$6$联通
即：只要保证每一个国王的左上、上、右上、左、右都没有其他的国王就行了
那么再简化一步说明，每一行的状态只与上一行的状态有关
显然这符合$dp$的原则：**无后效性**
**设状态$f[i][j][k]$表示当前在第i行，第i行的状态为j，已经放置了k个国王时的方案数**
由于只与上一行有关，那么只需要某个放国王的位置满足6联通内无其他国王就行了
不妨设本行状态为$x$，上一行状态为$y$
当 $x$&$y$或$x$&$(y<<1)$或$x$&$(y>>1)$时显然不合法，舍去（存在上3联通国王）
再有，对于某一个状态$i$，显然当$i$&$(i<<1)$时不合法，舍去（存在相邻的国王）
那么这时对于这些合法的可能状态有：
$f[i][x][t+Count(x)]=∑f[i-1][y][t]$
其中$t$为上一行放的国王总数，$Count(i)$表示状态$i$在二进制下的$1$的个数
那么目标状态即为$∑f[n][x][K]$
还是挺好理解的对吧~
为了优化常数，我们可以先预处理出一些合法的状态，存在一个数组里
那么我们的dp状态就可以更改成$f[i][j][k]$表示对于第$i$行，当前状态**编号为**$j$时已经用了$k$个国王的总方案数
那么状态转移和上面一样啦
别看我写的这么顺畅，其实做的时候连位运算还不是太理解，到底在干什么。。。
还有就是注意开$longlong$就没什么了
下面放一下A掉的code好了
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define re register
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline int read()
{
int p=0,f=1;re char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;}
const int maxn=11;
int n,K,lim,cnt,num[1<<maxn],can_use[1<<maxn];
ll f[maxn][1<<maxn][maxn*maxn],ans;
inline int Count(int s,int sum=0)
//计算状态s中有多少1(放了多少国王)
{
while(s)s&=(s-1),sum++;
return sum;
}
int main()
{
n=read(),K=read();
lim=(1<<n)-1;//满状态
for(re int i=0;i<=lim;i++)//预处理所有可行状态
if(!(i&(i<<1)))
can_use[++cnt]=i,num[cnt]=Count(i),f[1][cnt][num[cnt]]=1;
for(re int i=2;i<=n;i++)
for(re int j=1;j<=cnt;j++)
{
int x=can_use[j];
for(re int k=1;k<=cnt;k++)
{
int y=can_use[k];
if((x&y)||(x&(y<<1))||(x&(y>>1)))continue;
//两行之间状态不合法直接跳过
for(re int t=0;t<=K;t++)//累加方案
f[i][j][t+num[j]]+=f[i-1][k][t];
}
}
for(re int i=1;i<=cnt;i++)//将所有可行状态全部累加
ans+=f[n][i][K];
printf("%lld\n",ans);
return 0;
}
```
这题。。。可能很简单吧。。。~~（反正我写了1个多小时233）~~
貌似真的是一道很简单的状压dp了
===============================================================
### ex2：CF580D Kefa and Dishes
题目传送门：
https://www.luogu.org/problemnew/show/CF580D
感觉。。。这题是个很友好~~（毒瘤）~~的题了
翻译的人还好心的告诉我们要用状压。。。
这题在一般状压的基础上加了一点变化：状态之间有联系
题目中说：这$n$个菜有$k$个规则，如果kefa在吃完第$xi$个菜之后吃了第$yi$个菜（保证$xi$、$yi$不相等），那么**会额外获得**$ci$ $(0<=ci<=10^9)$的满意度
显然这是**与吃菜的顺序有关的**
但是再仔细考虑一下，会发现其实也是**没有后效性**的
因为**一道菜只与它前面的那道菜有关**
显然我们**可以枚举要吃的菜的前面那道菜**
不妨设状态$f[i][j]$表示当状态为$i$时，最后吃的一道菜为$j$时获得的最大满意度
如果设当前的状态为$x$，上一次的状态为$y$
显然对于一道我们要吃的菜$j$，在$x$中包含，在$y$中不能包含，而且必须对于某个菜$k$已经吃过
即：$i$&$(1<<j)$和$i$&$(1<<k)$时状态$i$才成立
同时当然也要保证$j!=k$
那么对于这些可行的状态有转移方程：
$f[i][j]=max(f[i$^$(1<<j)][k]+A[j]+w[k][j])$
显然当那些状态中存在$m$个$1$时（已经吃了$m$道菜）取$max$即为最后的答案
那么也就没什么了吧
下面放代码
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#define re register
using namespace std;
typedef long long ll;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()
{
int now=0,f=1;re char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;}
const int maxn=20;
int n,m,K,lim,A[maxn],mp[maxn][maxn];
ll f[1<<maxn][maxn],ans;
inline int Count(int s,int sum=0)
{
while(s)s&=(s-1),sum++;
return sum;
}
int main()
{
n=read(),m=read(),K=read();
for(re int i=0;i<n;i++)//初始状态:只吃一个
f[1<<i][i]=A[i]=read();
for(re int i=1;i<=K;i++)
{
int x=read()-1,y=read()-1,w=read();
mp[x][y]=w;
}
lim=(1<<n)-1;//满状态
for(re int i=0;i<=lim;i++)
{
int sum=Count(i);
for(re int j=0;j<n;j++)
{
if(!(i&(1<<j)))continue;//没吃过j不合法
for(re int k=0;k<n;k++)
{
if(j==k||(!(i&(1<<k))))continue;//相同或没吃过k不合法
f[i][j]=max(f[i][j],f[i^(1<<j)][k]+A[j]+mp[k][j]);
//dp转移方程
}
if(sum==m)ans=max(ans,f[i][j]);
//已经吃了m个菜就统计答案
}
}
printf("%lld\n",ans);
return 0;
}
```
这题还是很好理解的吧（至少比$ex1$好理解~）
===============================================================
### ex3：CF327E Axis Walking
题目传送门：
https://www.luogu.org/problemnew/show/CF327E
状压dp毒瘤题一道。。。
但是莫名感觉又占了一道黑题的便宜233~~（逃~~
这题很明了，一看就是状压dp
对于那些前缀和我们可以累加取得
不妨设$sum[i]$表示当状态为$i$时的前缀和
那么显然有$sum[i]=∑i$中为$1$的位置的$sum$
对于那些$sum[i]$为给定的数的状态显然要舍去
那么不妨再设$f[i]$为状态为$i$时的方案数
类似于$sum$的转移，显然有$f[i]=∑i$中为$1$的位置的$f$
发现这两者都需要访问那些状态$i$中的$1$的位置
那么对于这些状态$i$中那些为$1$的位置如何访问呢？
我们当然不能每次都让$i>>1$然后再判断这一位是否为$1$，因为这样太慢了
所以我们需要快速地访问那些$1$的位置
这时需要用到神奇~~（毒瘤）~~的位运算了
我们发现当$i$&~$lowbit(i)$时恰好能达到这一点
它**相当于把$i$最低位$1$以后的部分全部消去了**，相当于加速了我们的查找过程
于是乎，这题就与普通的状压dp无异了
放一下code吧
```cpp
#include<iostream>
#include<cstdio>
#define re register
using namespace std;
typedef long long ll;
const int inf=1e9+7;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline ll read()
{
ll now=0,f=1;re char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return 1ll*now*f;}
const int maxn=(1<<24)+3;
int n,k,lim,A[30],f[maxn];
ll no_permit[3],sum[maxn];
//f[i]表示状态为i时的方案数
//sum[i]表示状态为i时的前缀和
inline int lowbit(int x){return x&(-x);}
int main()
{
n=read();
for(re int i=0;i<n;i++)
sum[1<<i]=read();
k=read();
for(re int i=0;i<k;i++)
no_permit[i]=read();
f[0]=1,lim=(1<<n)-1;//满状态
for(re int i=1;i<=lim;i++)//枚举现在的状态
{
sum[i]=sum[i&~lowbit(i)]+sum[lowbit(i)];
if(sum[i]==no_permit[0]||sum[i]==no_permit[1])continue;
//不合法的状态排除
for(re int j=i;j;j-=lowbit(j))//枚举可能的上一次状态
f[i]=(f[i]+f[i&~lowbit(j)])%inf;
//快速累加所有可行的状态
//其中注意i&~lowbit(i)表示消去i二进制下lowbit后面的部分
//这样就可以直接快速访问那些为1的位置
}
printf("%d\n",f[lim]);
return 0;
}
```
可能。。。$lowbit$加速我现在也不太会用。。。
可以去看一看zsydalao写的题解 [链接](https://shehuizhuyihao.blog.luogu.org/solution-cf327e) 。。。可能我写的不是太好
大概是又水了一道黑题233
=================================================================
## 小结：
状压dp，一种神奇的、令人窒息的dp（大雾）
它可以让你当场秒懂，但实现起来懵逼且毫无头绪
尤其是令人作呕的位运算是它的一大杀手锏
但是我们相信，即使是再强的位运算也抵挡不住一颗勇往直前的心❤
或许当我真的成为一名有强大实力的OI选手，我可能会说：
“不就是状压dp么，看我秒切了它！”
可能这是后话了
stop！放一下鸡汤，还是说正经的。。。
虽说状压dp很难，也很不好想，但是NOIp近年确是有考到
比如
[宝藏](https://www.luogu.org/problemnew/show/P3959)
这题（还好我写过了233）
题目难度还是挺大的，也确实不是太好实现
可能想出了正解却不能很好地实现
况且状压不只应用在dp方面，其他的题目中也可能存在
比如一些题目，数据范围不小，根本不像是状压，但是却需要用到状压的思想来解决
这一点尤需注意
这篇状压的总结可能以后还会更新吧，但那些都是以后慢慢做的事情了
TSOI sjt 写于 2018年9月28日
别忘了给点个赞哟~QAQ
==============================================================
#### upd：2018年9月29日 上午
又找了一道 [马老师](https://www.luogu.org/space/show?uid=60124) 推荐的例题，早上切掉了233
~~（发现我现在写状压的题感觉很顺手）~~
### ex4：P3694 邦邦的大合唱站队
题目传送门：
https://www.luogu.org/problemnew/show/P3694
这题一看数据范围就知道是个状压
也没什么可说的，直接开讲好了
对于每个队伍，我们只关心它们最终有没有连在一起
不妨**设状态$f[i]$表示当所有的团队的连接状态为$i$时的最少出队人数**
显然，**目标状态**为$f[(1<<m)-1]$
那么不妨来思考一下如何进行$dp$转移
考虑到一个队伍$j$要连在一起，显然之前的状态是$i$中的第$j$位为$0$
即$i$^$(1<<j)$是i状态之前的状态，我们设为$k$好了
那么现在考虑一下，如何从状态$k$推到状态$i$呢
显然要把所有不是$j$队伍的人拿出队伍
那么拿出队伍的人数就是$num[j]-$属于$j$队伍在当前区间的人
对于这个当前区间内$j$队伍的人我们可以开一个二维数组$sum[x][i]$表示到位置$x$时队伍$i$的前缀和
那么**状态转移方程**为：$f[i]=$
$min(f[i$^$(1<<j)]+num[j]-(sum[now][j]-sum[now-num[j]][j]))$
那么。。。也就没什么了
注意数组下标就行了
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define re register
using namespace std;
typedef long long ll;
const int inf=1e9+7;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂
{
int now=0,f=1;re char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;}
const int maxn=100003;
const int maxm=23;
int n,m,lim,num[maxm],sum[maxn][maxm];
int f[1<<maxm];
//f[i]表示当状态为i时(各队伍的排队情况)所需出队的最少人数
int main()
{
n=read(),m=read();
for(re int i=1;i<=n;i++)
{
int x=read()-1;
num[x]++,sum[i][x]++;
for(re int j=0;j<m;j++)//前缀和
sum[i][j]+=sum[i-1][j];
}
memset(f,0x3f,sizeof(f));
f[0]=0,lim=(1<<m)-1;//满状态
for(re int i=1;i<=lim;i++)//枚举状态
{
int now_len=0;
for(re int j=0;j<m;j++)//找到现在的队伍长度
if(i&(1<<j))now_len+=num[j];
for(re int j=0;j<m;j++)
if(i&(1<<j))
f[i]=min(f[i],f[i^(1<<j)]+num[j]-(sum[now_len][j]-sum[now_len-num[j]][j]));
//状态转移:显然是由某一个上次没排好的队伍转移过来,要去掉整体的减去该区间内原来有的人数
}
printf("%d\n",f[lim]);
return 0;
}
```
那么。。。貌似又水了一道状压dp。。。（大雾）
仍然留坑。。。下次做完状压dp还加到这里来
================================================================
#### upd：2018年9月29日 下午
开始疯狂做状压dp。。。又做了一道。。。
### ex5：P3475 [POI2008]POD-Subdivision of Kingdom
题目传送门：
https://www.luogu.org/problemnew/show/P3475
一看题面。。。感觉很清新
但是发现竟然。。。没有数据范围！
虽然说我是专门找的状压dp的标签。。。但是我也是很在意数据范围的
于是就~~厚颜无耻地~~看了一看题解。。。发现$n<=26$
“直接上状压！”
开始我开开心心的写了个正常的状压，暴力枚举每一个可能的情况
结果算了一下空间和时间。。。发现$T$了，而且是$T$到死。。
回过头来仔细思考，发现这题貌似不用枚举所有的状态
其实**只要枚举一半的状态**
因为题目中说要“分成两部分”
所以显然**一部分与另一部分的状态是相互对应的**
那么。。。就又想到一个神奇的思路
不妨枚举第一部分的状态为$s1$，第二部分的状态为$s2$
显然当$s1$中有$n/2$个$1$时代表整张图被分成两部分
那么我们只需要**找到一种情况使得在分成两部分的情况下相连的边数最少**就行了
不妨设初始时，$s1$中没有点，$s2$代表整个集合
那么每次我们可以枚举一个点，让它**在$s2$中删去，加入到$s1$中**
同时当前的**总边数更新**为$sum-$该点之前与$s1$的连边$+$该点之后与$s2$的连边
对于这个“连边数”，我们可以**预处理（总共一半的）每个状态内的$1$的个数**
那么$num[s>>13]+num[s-((s>>13)<<13)]$即为连边数
所以，大致思路就是状压$+dfs$
放一下代码好了
```cpp
#include<iostream>
#include<cstdio>
#define re register
using namespace std;
const int inf=1e9+7;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂
{
int now=0,f=1;re char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;}
const int maxn=27;
int n,m,lim,p[maxn],num[(1<<(maxn>>1))+17],ans=inf,es,s1,s2;
inline int lowbit(int x)
{
return x&(-x);
}
inline void pre()//预处理一半的状态
{
lim=(1<<13)-1;
for(re int i=0;i<=lim;i++)
num[i]=num[i-lowbit(i)]+1;
}
inline int calc(int s)//计算集合中与另一个集合之间的连边数
{
return num[s>>maxn/2]+num[s-((s>>maxn/2)<<maxn/2)];
}
inline void dfs(int x,int k,int sum)
{
if(k==n/2)//已经分成了两部分：统计最优解
{
if(sum<ans)ans=sum,es=s1;
return ;
}
for(re int i=x+1;i<=n;i++)
{
int sum1=calc(p[i]&s1),sum2=calc(p[i]&s2);
//计算连边数
s1|=1<<(i-1);//从1集合加入i
s2^=1<<(i-1);//从2集合删去i
dfs(i,k+1,sum-sum1+sum2);
//更新状态继续搜索
s1^=1<<(i-1);//回溯
s2|=1<<(i-1);
}
}
int main()
{
n=read(),m=read();
pre();//预处理状态中的1的个数
for(re int i=1;i<=m;i++)
{
int x=read(),y=read();
p[x]|=1<<(y-1);
p[y]|=1<<(x-1);
}
s2=(1<<n)-1,dfs(0,0,0);
for(re int i=1;i<=n;i++)
if(1<<(i-1)&es)printf("%d ",i);
return 0;
}
```
其实这题还是挺好的
PS：~~不折半预处理或者数组开大了会T和M到死~~
=============================================================
#### upd：2018年9月29日 下午
### ex6：P3092 [USACO13NOV]没有找零No Change
题目传送门：
https://www.luogu.org/problemnew/show/P3092
~~（一道几乎是被我秒切的题）（逃~~
~~励志刷完所有的状压！~~（大雾）
可能我要做状压题做到死了233
不过真的很好想~~（感觉状压dp都是套路题）~~
这不，又~~（水）~~做完一道
这个题就是典型的状压$dp$了（一看题面就能看出来）
（貌似这是我15分钟写完的一道题了，不得不说真的好快。。。）
下面直接开讲（还有我的心路历程）
“一看K（硬币数）的范围这么小，肯定是个状压$dp$”
既然明确了是个状压$dp$，那么想一想如何设计状态和进行转移呢
题目中要求：**买完所有的物品之后剩下的最多钱数**
显然要设计一个状态
由于题目$K$很小$(K<=16)$，所以我们从$K$（硬币）下手
不妨**设状态$f[i]$表示使用硬币状态为$i$时能买到的最多商品数**
显然**目标状态为**$f[i]==n$时$min($总硬币价值$-i$中所用的硬币价值之和$)$
对于**一个硬币$j$，如果它在$i$状态中使用过**（对应位为$1$）
那么我们**可以由没用硬币$j$的状态转移到状态$i$**，即状态$(i$^$(1<<j))$
考虑到**花费硬币$j$后能买到的商品一定是所有商品中连续一段前缀**
其实**能买到的商品数就是这个前缀最后一个元素的下标**
那么到这里，$dp$的**转移方程**也就呼之欲出了：
$f[i]=max(f[i$^$(1<<j)]+$**在原来的基础上**使用硬币$j$最多能买到的商品数$)$
诶？这个“**在原来的基础上**”指的是什么呢？
其实**指的是在状态$i$^$(1<<j)$之前就已经买过的商品的总价值**
（已经买的商品显然就不用再买了啊QAQ）
而这些之前的总价值在数列中可以表示为连续的一段，即**前缀和**
那么上面其实就已经是一个可以实现的多项式做法了
但其实上式还可以优化
对于那些所有的满足条件的状态$i$^$(1<<j)$，都**存在着很多满足条件的原基础**，如果暴力的去扫描一个合理的最大位置，显然单次转移是$O(n)$的，那么总复杂度就是$O(2^K*n)$的，时间上不能接受
但因为我们要找“**最多能买到的商品数**”，显然是**取第一个小于等于"“原基础花费”+该硬币$j$"这个值的位置**
其实也就是前缀和数组中$sum[f[i$^$(1<<j)]]+coin[j]$的$upper$_$bound$
**为什么可以在前缀和数组中二分查找呢**？
因为每个商品最小代价为$1$，就保证了**前缀和数组单调上升**，所以**是可二分的**
那么对于所有这些可行的状态$i$^$(1<<j)$，我们就不必再一个一个枚举可行的最大位置，而是直接寻找上式的upper_bound就行了，单次转移的复杂度就降为了$O(logn)$，那么总复杂度为$O(2^k*logn)$
可能。。。到这里这题就讲完了吧。。。
这个优化还是挺重要的，没有它可能就会$T$到死
还有嘛。。。就是最开始我的二分初值打错了，没赋$0$，结果$RE$了一次
在函数内的变量也要注意初值，其实并不是$0$，小心哟！
下面放一下代码好了
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#define re register
using namespace std;
typedef long long ll;
const ll inf=7e9+7;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂
{
int now=0,f=1;re char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;}
const int maxK=18;
const int maxn=100003;
int K,n,tot,lim,A[maxK],sum[maxn],f[1<<maxK];
ll ans=inf;
inline int Binary_search(int x)//(upper_bound)二分查找第一个<x的数
{
int l=1,r=n,mid,p=0;//注意p的初值!不为0 #8会挂！
while(l<=r)
{
mid=(l+r)>>1;
if(sum[mid]<=x)l=mid+1,p=mid;
else r=mid-1;
}
return p;
}
int main()
{
K=read(),n=read();
for(re int i=0;i<K;i++)
{
A[i]=read();
tot+=A[i];
}
for(re int i=1;i<=n;i++)
sum[i]=sum[i-1]+read();
lim=(1<<K)-1;//满状态
for(re int i=0;i<=lim;i++)
{
for(re int j=0;j<K;j++)
if(i&(1<<j))//用过这个硬币
{
int pos=Binary_search(A[j]+sum[f[i^(1<<j)]]);
//在之前的状态中找到一个买东西数最多的状态更新
f[i]=max(f[i],pos);
}
if(f[i]==n)//当前状态恰好能买完所有东西
{
ll t=0;
for(re int j=0;j<K;j++)//累加所有用过的硬币
if(i&(1<<j))t+=A[j];
ans=min(ans,t);
}
}
if(ans>tot)printf("-1\n");//钱不够当然无解
else printf("%lld\n",tot-ans);//反之为最优解
return 0;
}
```
这题也不错，是一道状压$dp$练手好题
====================================================================
upd：2018年10月1日 上午
### ex7 P3451 [POI2007]ATR-Tourist Attractions
题目传送门：
https://www.luogu.org/problemnew/show/P3451
一道毒瘤卡空间题。。。调了一下午$+$一上午
本来还想早点写完之后看看别的东西来着~~（貌似这是状压dp的最后一题了）~~
不过不得不说题目还是很好的~~（虽然说我被卡了空间没过掉233）~~
来讲一下吧
看完这题我的心里是拒绝的。。。
题目很长，翻译不好，第一感觉题目很复杂
仔细读完题发现大概是有了思路
题目大意：
给你一张有$n$个点的无向图，起点为$1$，指定前$K$个点，要求按照必须给定的顺序经过前$K$个点（即对于一个点，必须先经过它之前的一些点再经过它），这些点可以重复经过，之后再到走$n$点，求整个过程的最短路
我们规定，$K<=20$且$n<=20000$
显然，这题和最短路有关，于是先从最短路下手
这些点是可以重复经过的，那么**对于一个指定的点，显然它之前的点怎么走都行**
这就需要求出两点之间的最短路了
可以用$SPFA$，也可以用堆优化的$diji$
那么又发现$K$很小，显然可以状压
不妨设状态$f[i][j]$表示经过指定的点状态为$i$，最后一个到达的点为$j$时的最短路
显然，这个状态没有后效性，可以继续递推出下一个状态
不妨枚举一个在$i$状态上下一个要去的点，设为$k$
显然$j!=k$（题目保证没有自环）
而且$k$必须满足所有它之前的点都被经过（已经属于状态集合中）才能进行转移
那么可以写出这样的转移方程：
$f[i|(1<<k-2)][k]=min(f[i][j]+dis[j][k])$
那么就可以转移了
目标状态即为$min(f[(1<<K)-1][i]+dis[i][n])$
（别忘了最后还要到$n$点）
特殊的，当$K=0$时（没有指定点）显然就是$dis[1][n]$直接输出即可
那么就可以做辣！
放一下代码好了（注意是$80$分，因为题目卡空间，过不掉）
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline int read()
{
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;}
const int maxn=20001;
const int maxm=200001;
const int maxK=20;
struct Edge
{
int from,to,w;
}p[maxm<<1];
int n,m,K,Q,cnt,lim,ans=inf,head[maxn],E[maxK+1],vis[maxn];
int d[maxK+1][maxK+1],dis[maxn],f[(1<<maxK)+1][maxK];
//f[i][j]表示状态为i时最后到达的点为j时的最短路
inline void add_edge(int x,int y,int W)
{
cnt++;
p[cnt].from=head[x];
head[x]=cnt;
p[cnt].to=y;
p[cnt].w=W;
}
inline void SPFA(int s)//其实这是堆优化之后的diji= =
{
priority_queue<pair<int,int> > q;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis));
dis[s]=0,q.push(MP(0,s));
while(!q.empty())
{
int x=q.top().second;
q.pop();
if(vis[x])continue;
vis[x]=1;
for(int i=head[x];i;i=p[i].from)
{
int y=p[i].to,t1=dis[x]+p[i].w;
if(dis[y]>t1)dis[y]=t1,q.push(MP(-dis[y],y));
}
}
for(int i=1;i<=K+1;i++)
d[s][i]=dis[i];
d[s][0]=dis[n];
}
int main()
{
// printf("%.2lfMB\n",(double)sizeof(f)/(1<<20)+(double)sizeof(d)/(1<<20));
n=read(),m=read(),K=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),w=read();
add_edge(x,y,w);
add_edge(y,x,w);
}
if(!K){SPFA(1);printf("%d\n",d[1][0]);return 0;}
for(int i=1;i<=K+1;i++)//预处理最短路
SPFA(i);
Q=read();
while(Q--)//统计连边数
{
int x=read(),y=read();
E[y]|=1<<(x-2);
}
memset(f,0x3f,sizeof(f));
f[0][1]=0,lim=(1<<K)-1;//初始状态和满状态
for(int i=0;i<=lim;i++)//枚举状态
{
for(int j=1;j<=K+1;j++)//枚举上一次最后到达的城市
if(f[i][j]<1e9)
{
for(int k=2;k<=K+1;k++)//枚举这次要去的城市
{
if(j!=k&&(i&E[k])==E[k])//满足条件
{
int t=i|(1<<(k-2));//新状态
f[t][k]=min(f[t][k],f[i][j]+d[j][k]);//更新为更优解
}
}
}
}
for(int j=1;j<=K+1;j++)//最终状态统计答案
if(f[lim][j]<1e9)
ans=min(ans,f[lim][j]+d[j][0]);
printf("%d\n",ans);
return 0;
}
```
一道$zz$题卡了差不多一天，最后也没做完。。。
上面的代码已经卡了一页多了。。。并不能$AC$
~~就算我A掉了这题吧~~（雾）
==============================================================
## 总结与反思：
发现状压$dp$很~~（毒瘤）~~好玩，总计刷了$3$天的状压题
可能还是有些题目我没见过，但是我觉得已经见过足够多的状压套路了
做了这么多经典的状压题目，我感觉状压是一种思想，一种处理问题的方法，而不是简简单单的只局限在$dp$方面
感觉。。。最深的体会可能也就是这句话了（对于状压$dp$）：
**“状压dp，没有改变dp本质的优化方法，阶段还是要照分，状态还是老样子，决策依旧要做，转移方程还是得列，最优还是最优，无后性还是无后性”**
毕竟**状压$dp$的本质还是$dp$，所以状压唯一的不同之处就在于使用位运算来简化条件和状态（而且数据范围很小）**
其实反过来想，所有的$dp$不都是这个样子么？
又想起之前听过的一段话：“**动态规划，本质就是一种简化问题的思路和方法，都是在原问题的基础上，忽略次要矛盾，关心主要矛盾，通过状态之间的转换和递推达到最终求解的目的**”
发现刷过一些状压$dp$的题后，对$dp$这种感觉和理解更加彻底了
大概所有的$dp$题都是这样的一个思想和套路了吧$QAQ$
况且，为了刷状压题，我发现我使用位运算的能力也提高了~~
（这也可能是我之前太菜了位运算用不好的原因）~~
一点不足就是，由于我做的题目都是状压$dp$，因此状压与其他算法的结合类的题目我见过和做过的和很少~~（甚至没有）~~
看来以后还是要多做一些状压题啊
$TSOI$ $sjt$ 写于$2018$年$10$月$1$日
~~（这可能是一个永远也填不完的坑了）~~