热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

状态压缩总结

本文主要是由Wiskey大神的博客的结合少许个人的总结,传送门概念:状态压缩是以二进制来保存每一个的状态,比如总共的物品有n件,那么我一共的状态有2^n次,最大的状态用二进制表示为11.

本文主要是由

Wiskey大神的博客的结合少许个人的总结,传送门

概念:
状态压缩是以二进制来保存每一个的状态,比如总共的物品有n件,那么我一共的状态有2^n次,最大的状态用二进制表示为11....n个1...11,经常得到这样的状态转移方程dp[11001] = dp[10001] + dp[11000] + dp[01001],当前状态只能由这些状态转移过来,相比较于一般的dp有什么优点呢?就在于二进制的位运算,一般的dp的话是用一个for循环来表示状态转移而二进制的速度快而且方便,注意位运算的优先级比较低,但是对于n比较大时,数组往往会开不下,所以一般n从1-20会选择使用状态压缩。

使用的范围:

根据二进制的特性,可以处理棋盘问题

1.简单棋盘问题

有n*n的一块棋盘,要往上面放n个棋子,同行同列不能有超过两个的棋子,问你有多少种方案

定义dp[i]表示状态为i的时候能放的种类数目,i其中的每一位表示的是列的编号,因为每一行只能放一个,所以状态转移的时候只要保证每一次都增加一个1就行了

这里有几个位运算的技巧

i)x&-x 可以得到x的从后往前的第一个非0的二进制 举个栗子 (注意二进制的位运算都是对于补码进行的)

x  原码 = 反码 = 补码 = 00101 

-x   原码 = 10101  反码 = 11010 补码 11011

x & -x = 00001

ii)i^x 可以得到i去掉这个x之后的数 假如i= 10110   x = 00100 那么异或一下就是 10010

这样就得到了前面一个状态,然后对于这个状态我们再让他进行与运算逐步得到所有的状态,直到这个i = 0

 代码:

#include
#include
#include
using namespace std;
const int maxn = 1 <<20;
int dp[maxn];
int main()
{
    int n;
    while(~scanf("%d",&n)){
        memset(dp,0,sizeof(dp));
        int i,tmp = (1 < 

2.对于有限制的棋盘问题(保证每一行都有一个能放)

#include
#include
#include
#include
const int maxn = 1 <<20;
int dp[maxn];
int map[20][20];
int a[20];
int n;
int main()
{
    while(~scanf("%d",&n)){
        for(int i = 1; i <= n ;i++){
            a[i] = 0;
            for(int j = 1; j <= n;j++){
                map[i][j] = rand()%2;
                a[i] = a[i]*2 + map[i][j];
                printf("%d",map[i][j]);
            }
            printf("\n");
        }
    int i,tmp = (1< 

3.给出一个n*m的棋盘(n,m <= 80),要在棋盘上放 k(k<=20) 个棋子,使得任意两个棋子不相临。问你方案种数。

定义dp[i][j][k]表示当前位于第i行时状态为s[j]棋子数目为k的种类数目,最后只要遍历所有可能的s[j]情况就是答案

状态转移方程  dp[i][j][k] += dp[i][p][k-c[j]](所有的p的可能性)只要满足 (s[j]&s[p]) == 0

#include
#include
#include
using namespace std;
const int maxn = 1 <<10;
int s[105],c[105],dp[15][105][10];
int n,m,pn;
int top;
void dfs(int t,int state,int count,int *flag)
{
    if(t == m){
        s[++top] = state;
        c[top] = count;
        return ;
    }
    flag[t+1] = 0;
    dfs(t+1,state*2,count,flag);
    if(flag[t] == 0){
        flag[t+1] = 1;
        dfs(t+1,state*2 + 1,count+1,flag);//flag表示当前是第几个为了保证flag[t] = 0,flag[t+1] = 1
    }
}
int main()
{
    while(~scanf("%d%d%d",&n,&m,&pn)){
        int flag[20] = {0};
        top = 0;
        if(n = c[j] + c[p])
                            dp[i][j][k] += dp[i-1][p][k-c[j]];
                    }
                }
            }
        }
    int sum = 0;
    for(int i = 1; i <= top; i++){
        sum += dp[n][i][pn];
    }
    printf("%d\n",sum);
}
return 0;
}

4.在n*n(n≤10)的棋盘上放k个国王(可攻击相邻的8个格子),求使它们无法互相攻击的方案数。

#include
#include
#include
using namespace std;
const int maxn = 1 <<10;
int s[105],c[105],dp[15][105][10];
int n,pn;
int top;
void dfs(int t,int state, int count,int *flag)
{
    if(t == n){
        s[++top] = state;
        c[top] = count;
        return ;
    }
    flag[t] = 0;
    dfs(t+1,state*2,count,flag);
    if(flag[t-1] == 0 || t == 0){
        flag[t] = 1;
        dfs(t+1,state*2+1,count+1,flag);
    }
}
int main()
{
    while(~scanf("%d%d",&n,&pn)){
        int flag[20] ={0};
        top = 0;
        dfs(0,0,0,flag);
        //printf("%d\n",top);
        memset(dp,0,sizeof(dp));
        dp[0][1][0] = 1;
        for(int i = 1; i <= n ;i++){
            for(int j = 1; j <= top ;j++){
                for(int p = 1; p <= top; p++){
                    for(int k = c[j]; k <= pn; k++){
                        if((s[p]&s[j])||(s[j]&s[p]<<1)||(s[j]&s[p]>>1))
                            continue;
                            if(k >= (c[p] + c[j]))
                            dp[i][j][k] += dp[i-1][p][k-c[j]];
                    }
                }
            }
        }
        int sum = 0;
        for(int i = 1; i <= top;i++)
          sum +=  dp[n][i][pn] ;
        printf("%d\n",sum);
    }
    return 0;
}

  

 


推荐阅读
author-avatar
mobiledu2502860983
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有