简易状压DP
开头甩定义

借助二进制完成对状态的压缩，从而进行动态规划的过程，我们称之为状态压缩动态规划（简称“状压DP”）

康康目录
简易状压DP
位运算
状压DP

位运算


左移右移

左移：左移一位，等价于该数x2

eg.  110<<1 = 1100 (十进制从6变为12)

右移同理

eg. 110>>1 = 11(十进制从6变为3)


与或非

相信各位OIer应当在普及时就学过位运算了，但本蒟蒻还是要讲

与：按位进行与运算 满足两数同一位都为1时结果为1，否则为0

或：按位进行或运算 满足两数同一位都为0时结果为0，否则为1

非：按位取反


简单运算

当我们需要判断或修改二进制数S的第i位时，我们进行以下操作

若判断第i位是否为0  即判断 (S&(1<<i)) 是否为0

若要将第i位设置为1 即 (S|(1<<i)) 即1左移i位于S进行或运算

若要将第i位设置为0 即 (S&~(1<<i)) 即S与只有第i位为0的数进行或运算


简单应用

经过上面的学习大家可以发现我们可以用位运算的方法来枚举子集

假设集合A={1,2,3,4,5}

我们可以通过将A中的数编号的方式使其转化为一个二进制数

是不是非常神奇呀

下面我们来康康具体操作

假设我们要表示A的子集B={2,4,5}






二进制数位
4
3
2
1
0




二进制值
1
1
0
1
0


子集元素
5
4
0
2
0


这里需要注意的是二进制的数位是从0开始的，所以对应关系不要找错

所以B集合用二进制就可以表示为11010啦！！
那么我们来做个练习
李白打酒  【2014蓝桥杯预赛】

话说大诗人李白，一生好饮。

一天，他提着酒壶，从家里出来，酒壶中有酒两斗。他边走边唱：

无事街上走，提壶去打酒

逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。请你计算李白有多少种满足要求的遇到店和花的可能情况

输入

无

正确输出

14
题解：

一道简单的练手题

考虑使用01串表示遇到花或者店，因为最后一个一定是花所以枚举14位01串就OK

代码放送~
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int ans=0;
	for(int i=0;i<(1<<14);i++)//枚举每种情况
	{
		int ans1=0,ans2=0;
		int num=2;
		for(int j=0;j<14;j++)
		{
			if(i&(1<<j))
			{
				ans1++;
				num*=2;
			} 
			else {ans2++;num--;}
		}
		if(ans1==5&&ans2==9&&num==1)ans++;//特判
	}
	cout<<ans;
}

好的你已经掌握了基本的位运算知识了让我们来康康简单状压DP
状压DP
话不多说直接上题
国王 [SGU 223]

在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数

输入

只有一行，包含两个整数 n 和 k
输出

每组数据一行为方案总数，若不能够放置则输出 0
样例输入

3 2

样例输出

16
1<=n<=10 , k<=n2
题解

本题为状态压缩DP入门题

这个题使用八皇后做法是显然不行的(很难剪枝)，就考虑使用DP，然而国王在棋盘上的状态使用传统的f[i][j]很难表示，由于国王的状态只有两种，放置与不放置，所以考虑状压解决

对于第i行所摆放的国王，只会有第i-1行和第i+1行的国王影响它，对其的影响是i-1行和i+1行的摆放方式和1~i-1行总共摆放的国王数很容易得出初始的动态方程

令f[i][j][s]为第i行目前摆放状态a[j]和前i行已经摆放的国王个数s，易得

f[i][j][s]=∑f[i-1][k][t]

a[j],a[k]为两种不同摆放方式

那么接下来我们就要想想如何表示这两种状态

还记得我们之前说的李白问题吗？不记得就回去看

看见国王在棋盘上摆放的状态只有两种，摆与不摆，那么我们可以尝试使用一个01串表示状态，又因为一排最多10个格子，最大宽度也满足，考虑：

（蒟蒻表格，@代替下国王，没有就是x）




@
x
x
x
@
x




1
0
0
0
1
0


如上图，每个格子对应一个二进制位，于是乎状态就可以用一个卡哇伊的 二进制数表示出来啦

时间复杂度也是允许的，可以自己推推看~

放代码！！
#include<bits/stdc++.h> //万能库深得朕心
using namespace std;
typedef long long ll;
#define N 15
ll f[N][155][155],ans=0,s=0;
int n,sum[166],num[155],K;
int main()
{
    cin>>n>>K;
	memset(f,0,sizeof(f));
	for(int i=0;i<(1<<n);i++)
	{
		if(i&(i<<1)) continue; //检查状态
		int k=0;
		for(int j=0;j<n;j++) if(i&(1<<j))k++;
		sum[++s]=i;
		num[s]=k;
    }
    
	f[0][1][0]=1;
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=s;j++)
	    for(int k=0;k<=K;k++)
	    {
	    	if(k>=num[j])
	    	for(int t=1;t<=s;t++)
	    	if(!(sum[t]&sum[j])&&!(sum[t]&(sum[j]<<1))&&!(sum[t]&(sum[j]>>1)))
	    	  f[i][j][k]+=f[i-1][t][k-num[j]];
		}
	
	for(int i=1;i<=s;i++) ans+=f[n][i][K]; //统计
	cout<<ans<<endl;
}

是不是有点感觉了

还要多练练题，基础的思路就是判断状态是否可以转化为二进制，推导dp方程然后写就完事

PS：位运算一定要好好记:) （惨痛教训）

附注：压缩BCD码与非压缩BCD码的区别—— 压缩BCD码的每一位用4位二进制表示，一个字节表示两位十进制数。例如10010110B表示十进制数96D；非压缩BCD码用1个字节表示一位十进制数，高四位总是0000，低4位的0000~1001表示0~9.例如00001000B表示十进制数8.

BCD码的运算法则

BCD码的运算规则：BCD码是十进制数，而运算器对数据做加减运算时，都是按二进制运算规则进行处理的。这样，当将 BCD码传送给运算器进行运算时，其结果需要修正。修正的规则是：当两个BCD码相加，如果和等于或小于 1001(即十进制数9)，不需要修正；如果相加之和在 1010 到1111(即十六进制数 0AH～0FH)之间，则需加 6 进行修正；如果相加时，本位产生了进位（十六制进位2020.1.15），也需加 6 进行修正。这样做的原因是，机器按二进制相加，所以 4 位二进制数相加时，是按“逢十六进一”的原则进行运算的，而实质上是 2 个十进制数相加，应该按“逢十进一”的原则相加，16 与10相差 6，所以当和超过 9或有进位时，都要加 6 进行修正。下面举例说明。

【例 1.3】 需要修正 BCD码运算值的举例。

(1) 计算 5+8；(2) 计算 8+8

解：(1) 将 5 和 8 以 8421 BCD输入机器，则运算如下：

0 1 0 1

+) 1 0 0 0

1 1 0 1 结果大于 9

+) 0 1 1 0 加 6 修正

1 0 0 1 1 即13 的 BCD码

结果是 0011，即十进制数3，还产生了进位。5+8=13，结论正确。

(2)将8以8421 BCD输入机器，则运算如下：

1 0 0 0

+）1 0 0 0

1 0 0 0 0产生进位   （十六制进位，2020.1.15）

+）0 1 1 0 加6修正

1 0 1 1 0 16的BCD码

结果是0110，即十进制的6，而且产生进位。8+8=16，结论正确。

微机原理代码： （AL=BCD 5，BL=BCD 8） 设AH=0，则

ADD AL,BL

AAA

结果为 AX=0103H,表示非压缩十进制数，CF=1，AF=1，AH=1，AL=3

使用AAA指令，可以不用屏蔽高半字节，只要在相加后立即执行AAA指令，便能在AX中得到一个正确的非压缩十进制数

压缩BCD码用4位2进制表示,1字节表示2位BCD码
如10010011B表示十进制数93
非压缩BCD码用1字节表示





BCD码是一一对应的，如：十进制的123 用BCD表示为:0001 0010 0011因为:十进制的 1 用二进制表示是 0001十进制的 2 用二进制表示是 0010十进制的 3 用二进制表示是 0011与二进制的区别：123的二进制应该用短除法求得1111011由此可见，BCD码只是机械地用二进制表示十进制的每一位。压缩与非压缩：由于1字节有8bit(8个0或1)如果用一字节存储4位BCD码(其余补0)就是非压缩如 十进制的123：00000001 00000010 0011如果用一字节存储8位BCD码就是压缩如
 十进制的123：0001 0010 0011





4位BCD码 8421  8位BCD码 8421 8421 


C语言压缩bcd码




[cpp] 
view plain 
copy 

#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
  
/* 
* 字符串转成bcd码，这个是正好偶数个数据的时候，如果是奇数个数据则分左靠还是右靠压缩BCD码 
*/  
int asc_to_bcd(char * dest,const char *src)  
{  
    unsigned char temp;  
    while(*src !='\0')  
    {  
        temp = *src;  
        *dest |= ((temp&0xf)<<4);  
        src++;  
        temp = *src;  
        *dest |= (temp&0xf);  
        src++;  
        dest++;  
    }  
    return 0;  
}  
  
int asc_to_bcd_right(char *dest,const char *src,int src_len)  
{  
    unsigned char temp;  
    if((src_len %2) !=0)  
    {  
        *dest &= 0;  
        temp = *src;  
        *dest |= (temp&0xf);  
        src++;  
        dest++;  
    }  
    asc_to_bcd(dest,src);  
    return 0;  
}  
  
int asc_to_bcd_left(char *dest,const char *src,int src_len)  
{  
    unsigned char temp;  
    if((src_len %2) !=0)  
    {  
        dest[src_len-1] &=0;  
    }  
    asc_to_bcd(dest,src);  
    return 0;  
}  
  
void print_hex(char * bcd,int len)  
{  
    int i=0;  
    for(i=0;i<len;i++)  
    {  
        int n = 8;  
        while(n--){  
            if((bcd[i] & (0x1<<n))==0)  
                printf("0");  
            else  
                printf("1");  
        }  
        putchar('\n');  
    }  
}  
  
  
int bcd_to_asc(char *dest,const char *src,int src_len)  
{  
    unsigned char temp;  
    char *t = dest;  
    while(src_len--)  
    {  
        *t |= ((*src&0xf0)>>4);  
        *t++ |= 0x30;  
        *t |= (*src&0xf);  
        *t++ |= 0x30;  
        src++;  
    }  
    return 0;  
}  
  
int left_bcd_to_asc(char *dest,const char * src,int src_len)  
{  
    bcd_to_asc(dest,src,src_len);  
    dest[src_len*2 -1] = '\0';  
  
    return 0;  
}  
  
  
int right_bcd_to_asc(char *dest,const char * src,int src_len)  
{  
    bcd_to_asc(dest,src,src_len);  
  
    memmove(dest,dest+1,src_len*2-1);  
    dest[src_len*2-1] = '\0';  
    return 0;  
}  
  
  
int main(void)  
{  
    char str[100];  
      
    char *str1 = "1234567";  
    int str_len = strlen(str1);  
    int bcd_len = (str_len+1)/2;  
    char *bcd = (char *)malloc(bcd_len);  
    printf("str_len = %d \n",str_len);  
    printf("bcd_len = %d \n",bcd_len);  
    memset(bcd,0,bcd_len);  
    memset(str,0,100);  
  
#if 0  
    printf("右靠\n");  
    asc_to_bcd_right(bcd,str1,str_len);  
    print_hex(bcd,bcd_len);  
    right_bcd_to_asc(str,bcd,bcd_len);  
    printf("str = %s\n",str);  
#endif  
  
#if 1  
    printf("左靠\n");  
    asc_to_bcd_left(bcd,str1,str_len);  
    print_hex(bcd,bcd_len);  
    //memset(str,0,100);  
    left_bcd_to_asc(str,bcd,bcd_len);  
    printf("str = %s\n",str);  
#endif  
    return 0;  
}  

压缩BCD码用4位2进制表示,1字节表示2位BCD码
如10010011B表示十进制数93
非压缩BCD码用1字节表示




BCD码是一一对应的，如：十进制的123 用BCD表示为:0001 0010 0011因为:十进制的 1 用二进制表示是 0001十进制的 2 用二进制表示是 0010十进制的 3 用二进制表示是 0011与二进制的区别：123的二进制应该用短除法求得1111011由此可见，BCD码只是机械地用二进制表示十进制的每一位。压缩与非压缩：由于1字节有8bit(8个0或1)如果用一字节存储4位BCD码(其余补0)就是非压缩如 十进制的123：00000001 00000010 0011如果用一字节存储8位BCD码就是压缩如 十进制的123：0001 0010 0011







4位BCD码 8421  8位BCD码 8421 8421 




C语言压缩bcd码





#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/*
* 字符串转成bcd码，这个是正好偶数个数据的时候，如果是奇数个数据则分左靠还是右靠压缩BCD码
*/
int asc_to_bcd(char * dest,const char *src)
{
	unsigned char temp;
	while(*src !='\0')
	{
		temp = *src;
		*dest |= ((temp&0xf)<<4);
		src++;
		temp = *src;
		*dest |= (temp&0xf);
		src++;
		dest++;
	}
	return 0;
}

int asc_to_bcd_right(char *dest,const char *src,int src_len)
{
	unsigned char temp;
	if((src_len %2) !=0)
	{
		*dest &= 0;
		temp = *src;
		*dest |= (temp&0xf);
		src++;
		dest++;
	}
	asc_to_bcd(dest,src);
	return 0;
}

int asc_to_bcd_left(char *dest,const char *src,int src_len)
{
	unsigned char temp;
	if((src_len %2) !=0)
	{
		dest[src_len-1] &=0;
	}
	asc_to_bcd(dest,src);
	return 0;
}

void print_hex(char * bcd,int len)
{
	int i=0;
	for(i=0;i<len;i++)
	{
		int n = 8;
		while(n--){
			if((bcd[i] & (0x1<<n))==0)
				printf("0");
			else
				printf("1");
		}
		putchar('\n');
	}
}


int bcd_to_asc(char *dest,const char *src,int src_len)
{
	unsigned char temp;
	char *t = dest;
	while(src_len--)
	{
		*t |= ((*src&0xf0)>>4);
		*t++ |= 0x30;
		*t |= (*src&0xf);
		*t++ |= 0x30;
		src++;
	}
	return 0;
}

int left_bcd_to_asc(char *dest,const char * src,int src_len)
{
	bcd_to_asc(dest,src,src_len);
	dest[src_len*2 -1] = '\0';

	return 0;
}


int right_bcd_to_asc(char *dest,const char * src,int src_len)
{
	bcd_to_asc(dest,src,src_len);

	memmove(dest,dest+1,src_len*2-1);
	dest[src_len*2-1] = '\0';
	return 0;
}


int main(void)
{
	char str[100];
	
	char *str1 = "1234567";
	int str_len = strlen(str1);
	int bcd_len = (str_len+1)/2;
	char *bcd = (char *)malloc(bcd_len);
	printf("str_len = %d \n",str_len);
	printf("bcd_len = %d \n",bcd_len);
	memset(bcd,0,bcd_len);
	memset(str,0,100);

#if 0
	printf("右靠\n");
	asc_to_bcd_right(bcd,str1,str_len);
	print_hex(bcd,bcd_len);
	right_bcd_to_asc(str,bcd,bcd_len);
	printf("str = %s\n",str);
#endif

#if 1
	printf("左靠\n");
	asc_to_bcd_left(bcd,str1,str_len);
	print_hex(bcd,bcd_len);
	//memset(str,0,100);
	left_bcd_to_asc(str,bcd,bcd_len);
	printf("str = %s\n",str);
#endif
	return 0;
}