状压DP学习笔记

crescentic · 2020-09-10 21:52:08 · 个人记录

前言：

最近学了这个神奇的东东，真的好难啊~[仙女叹气]~~

感觉自己没大理解，就写笔记强迫自己学会吧QAQ

定义：

状态压缩动态规划，就是我们俗称的状压DP，是利用计算机二进制的性质来描述状态的一种DP方式。

自己的小理解：其实就是将状态压缩成二进制下的数（1/0）来表示不同情况，进行DP……

前置知识：

• 二进制 和 位运算；
• 以及一个聪明的小脑袋瓜；

位运算介绍：

一个神奇的东西……

推荐博客

状压DP里主要用到的几个技巧见下图：

引入：

题目 ：互不侵犯

题意简述：

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到他周围的8个格子。

题目分析：

状态转移方程：

讲解都在代码里

完整代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
double p[25][25],dp[1 << 20];//dp[i],出现i状态的概率（1:这条鱼活着/0:它被吃啦） 
int c(int x) {//计算1的个数 
    int res = 0;
    while(x) {
        res += (x & 1);
        x >>= 1;
    }
    return res;
}
int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++)
            scanf("%lf",&p[i][j]);
    int num = (1 << n) - 1;
    dp[num] = 1;//初始状态，全部鱼都活着的概率为1
    for(int i = num - 1; i; i --) {//倒序枚举状态，鱼越吃越少，1的数量也越来越少……这残忍的现实！ 
        int cnt = c(i);//活着的鱼的数量 
        for(int j = 1; j <= n; j ++) {//枚举这一轮被吃到的鱼的序号 
            if((i & (1 << (j - 1)))) continue;//如果在当前状态下，j为1（鱼没有被吃了），跳过
            for(int k = 1; k <= n; k ++) {//枚举k条鱼吃掉的鱼的编号 
                if(!(i & (1 << (k - 1)))) continue;//如果在当前状态下，k为0（鱼已经被吃了,k吃不到j），跳过
                dp[i] += dp[i | (1 << (j - 1))] * p[k][j] / (1.0 * (cnt + 1) * cnt / 2.0);
                //否则，概率为 当前概率 加上 j位存活时的概率 * k条鱼吃掉j条鱼的概率 * 在所有活着的鱼中恰好选到j,k的概率。 
            }
        }
    }
    for(int i = 0; i < n; i ++) printf("%.6lf ",dp[1 << i]);//只有当前位为1的状态 
    return 0;
}

题目三 ：奖励关

题意简述：共有K轮，有n种物品，每一轮出现每一种物品的概率\frac{1}{n}，物品可选可不选，对于选每一种物品，必须要在前面的轮先选给定的部分物品，每一种物品的价格可正可负。求 k轮后按最优方案选择的期望价格。

数据范围：1\leq K \leq 100 ,1 \leq n \leq 15 1≤K≤100,1≤n≤15.

思路：

首先看题，概率dp没得跑。

再看数据范围，哦豁！状压dp！

这道题不同的是需要倒推，因为正推的话有些情况在转移时选择宝物的概率并不是平均的（有宝物合集的限制），这样就会导致结果出现问题，且最终答案的状态表示十分麻烦（不要问我是怎么知道的！），因此选择倒推。

另外，因为dp的转移至于当前局和前一局有关，所以可以用滚动数组优化一下。

详细讲解都在代码里啦~

完整代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int K,n,x,w[20],num[20];
double p,dp[2][1 << 15];
int main() {
    scanf("%d %d",&K,&n);
    p = 1.0 / n;//选择宝物的平均概率 
    for(int i = 1; i <= n; i ++) {
        scanf("%d",&w[i]);//分值 
        while(~scanf("%d",&x) && x)
            num[i] += 1 << (x - 1);//用二进制数存储 宝物集合 
    }
    int maxn = 1 << n;
    for(int i = K; i >= 1; i --) { //游戏轮数 
        for(int j = 0; j < maxn; j ++) {
            dp[i & 1][j] = 0;//初始化（清空上一次循环的值） 
            for(int k = 1; k <= n; k ++) {//枚举这轮抽到的宝物 
                if((j & num[k]) == num[k])//如果满足k宝物的 宝物集合要求,
                    dp[i & 1][j] += max(dp[(i + 1) & 1][j | (1 << (k - 1))] + w[k],dp[(i + 1) & 1][j]);
                    //满足最优策略，在拿k宝物和不拿之间选最大值 
                else dp[i & 1][j] += dp[(i + 1) & 1][j];//不满足的话，该状态及为上一次的状态，没有变化 
            }
            dp[i & 1][j] *= p;//最终期望要乘上随机选择一个宝物的概率 
        }
    } 
    printf("%.6lf",dp[1][0]);
    //因为是倒推的，所以最后答案为游戏开始时，未得到任何一个宝物的情况 
    return 0;
} 

题目四 ：Survival

题意简述：有n个Boss,其中有n-1个小boss必须先全部打完才能打第n个大BOSS，打一个小boss要耗体能usei，打完后恢复一部分vali，一开始体能为100，在打的过程中也最多为100，问能打完全部的BOSS? 能 输出clear!!! 否则输出try again.

思路：

很板的一道题