浅谈一类dp问题----状压dp

· · 个人记录

浅谈一类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

是不是感觉有上面的话有点熟悉？

（我是不会告诉你这是我从 这里 搬过来的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好了

#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即为最后的答案

那么也就没什么了吧

下面放代码

#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吧

#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写的题解 链接 。。。可能我写的不是太好

大概是又水了一道黑题233

=================================================================

小结：

状压dp，一种神奇的、令人窒息的dp（大雾）

它可以让你当场秒懂，但实现起来懵逼且毫无头绪

尤其是令人作呕的位运算是它的一大杀手锏

但是我们相信，即使是再强的位运算也抵挡不住一颗勇往直前的心❤

或许当我真的成为一名有强大实力的OI选手，我可能会说：

“不就是状压dp么，看我秒切了它！”

可能这是后话了

stop！放一下鸡汤，还是说正经的。。。

虽说状压dp很难，也很不好想，但是NOIp近年确是有考到

比如 宝藏 这题（还好我写过了233）

题目难度还是挺大的，也确实不是太好实现

可能想出了正解却不能很好地实现

况且状压不只应用在dp方面，其他的题目中也可能存在

比如一些题目，数据范围不小，根本不像是状压，但是却需要用到状压的思想来解决

这一点尤需注意

这篇状压的总结可能以后还会更新吧，但那些都是以后慢慢做的事情了

TSOI sjt 写于 2018年9月28日

别忘了给点个赞哟~QAQ

==============================================================

upd：2018年9月29日 上午

又找了一道 马老师 推荐的例题，早上切掉了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]))

那么。。。也就没什么了

注意数组下标就行了

#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

放一下代码好了

#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，小心哟！

下面放一下代码好了

#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分，因为题目卡空间，过不掉）

#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，因此状压与其他算法的结合类的题目我见过和做过的和很少（甚至没有）

看来以后还是要多做一些状压题啊

~~（这可能是一个永远也填不完的坑了）~~