首页 > 其他分享 >状压dp

状压dp

时间：2024-02-28 20:56:01浏览次数：24  
标签：表示 状态 int 状压 x2 x1 dp

0.位运算

1.概述

用01数字标志状态

2.要求

  • 对象状态只能有两种，例如放/不放，正/反等等

  • 某一项指标的范围很小

3.实际运用

后续\(S_i\)一般表示状态（除特殊说明）

特殊方格棋盘

click

组合：我会！\(n!\)

先考虑所有格子都能放

\(n \leqslant 20\)，可以状压

\(0\)表示没放，\(1\)表示放了

由于位运算的尿性，最右边是第一列，从右往左算

对于状态\(01101\)，就表示放了\(1,3,4\)列

由于一行只能放一个，上述状态表示第三行，那么

\[f(01101) = f(01100) + f(01001) + f(00101) \]

更进一步的，对于数\(s\)，如果某一位是\(1\)，那么就可以从这一位为0的状态转移而来

用位运算就是：

\[f_s +=f_{s - 2^i}(s >> i \& 1 = 1) \]

答案就是\(f(11111) = f(2^n-1)\)

但有的格子不能放了

那么首先，我们把不能放的状态也压缩

比如\(a[3]=00100\)就表示第三行第三列不能放

然后对于枚举的状态\(s\)，进行如下操作：

\[s \& (\sim a_i) \]

解释：\(a_i\)取反后被标记为不能放的列一定是\(0\)，再按位与就让\(s\)中同列的位置也变为\(0\)，就相当于不能放

更多的，对于快速求得哪一位是\(1\),可以使用\(lowbit\) 啊？

for(int i = 1;i <= m;i++)
{
	scanf("%d%d",&x,&y);
	a[x] |= (1 << (y - 1));// 把不能放的位置标记为1 
}
f[0] = 1;
//cout << 114 << endl;
for(int i = 1;i <= res;i++)
{
	int u,num = 0;
	for(u = i;u;u -= lowbit(u)) num++;//统计1的个数，也就是当前的i表示第几行 
	u = i & (~a[num]);//把不能放的位置变成0 
	while(u)
	{
		//cout << 114 << endl;
		//用lowbit提取u中的1，即100... 
		f[i] += f[i ^ lowbit(u)];// 只有i的这一列不为1才能加 
		u -= lowbit(u); 
	}
}

P1879 [USACO06NOV] Corn Fields G

click

首先将能不能种草压缩

for(int i = 1;i <= n;i++)
{
	for(int j = 1;j <= m;j++)
	{
		int x;
		scanf("%d",&x);
		a[i] = (a[i] << 1) + x;
	}
}

设\(dp_{i,s}\)表示第\(i\)行状态为\(S\)时的方案数

对于枚举的状态\(S\)，如果存在\(11\)之类的非法情况，那么

\[S \& (S << 1) = 1 \]

为了避免上下相邻，我们取得\(i-1\)行的状态\(S'\)，如果上下相邻，那么二者必有一位均是1，即

\[S \&S' = 1 \]

方程就是

\[dp_{i,S}+=dp_{i-1,S'}(S\&S'!=1) \]

for(int i = 1;i <= n;i++)
{
	for(int j = 0;j <= (1 << m) - 1;j++)
	{
		int u = j;
		if(u & (u << 1)) continue;//排除左右相邻
		if(a[i] == (a[i] | u))
		{
			vis[i][u] = 1; //标记合法，留着后面取用
			for(int k = 0;k <= (1 << m) - 1;k++)
			{
				if(k & (k << 1)) continue;
				int v = k;
				if(!vis[i - 1][v]) continue;//不合法
				if(u & v) continue;//排除上下相邻
				dp[i][u] = (dp[i][u] + dp[i - 1][v]) % mod;
			}
		}	
	}
}

P1896 [SCOI2005] 互不侵犯

click

用\(0/1\)表示有没有放国王

设\(dp_{i,j,S}\)表示放到第\(i\)行，用了\(j\)个国王，第\(i\)行的状态为\(S\)

接下来看转移条件

如果一个国王在第\(i\)行放在了第\(j\)列，那么对第\(i + 1\)行来说，第\(j - 1,j,j + 1\)列均不能放国王

接下来考虑用位运算排除情况

设当前第\(i\)行状态为\(S_i\)，上一行状态为\(S_{i-1}\)

如果第\(j-1\)列有国王，可以右移一下

\[(S_i >> 1) \& S_{i - 1} = 1 \]

类似可得：

第\(j\)列有国王：\(S_i \& S_{i-1} = 1\)

第\(j + 1\)列有国王：\((S_i << 1)\&S_{i-1} = 1\)

转移条件就是上述三个式子的值均不为1

考虑方程式

发现前两维很像背包

第\(i\)行放的棋子就是\(S_i\)中\(1\)的个数,设为\(num_{S_i}\)

\[dp_{i,j,S_i} += dp_{i - 1,j - num_{S_i},S_{i-1}} \]

初始化：\(dp_{0,0,0} = 1\)

技巧：我们可以预处理出来一堆左右不相邻的合法状态备用，可以避免盲目暴力

P2704 [NOI2001] 炮兵阵地

click

又一道经典的入门题

放为\(1\)，不放为\(0\)

根据炮兵射程可得

  • 连续三格内只能有一个阵地

横向判定就是分别左移一位和两位再分别取与

\[(S << 1) \& S=(S << 2) \&S = 0 \]

纵向判定涉及到三行，所以\(dp\)中要多一些行的状态

设\(dp_{i,S_i,S_j}\)表示到了第\(i\)行，当前行的状态是\(S_i\)，上一行的状态是\(S_j\)

那么转移就是\(dp_{i-1,S_j,S_k} \to dp_{i,S_i,S_j}\)，判定的三行分别是\(S_i,S_j,S_k\)

由于连续三格在同一列，所以直接取与就行

\[S_i\&S_j=S_i\&S_k=S_j\&S_k = 0 \]

转移方程：

\[dp_{i,S_i,S_j} = \max{(dp_{i-1,S_j,S_k})} \]

取答案时要遍历所有可能状态

由于第一、二行上面不足两行，需要单独处理

for(int i = 1;i <= tot;i++)
{
	if((a[1] | S[i]) == a[1])
	{
		vis[1][S[i]] = 1;
		dp[1][S[i]][0] = num[S[i]];
	}
}//第一行，就是初始化
for(int i = 0;i <= tot;i++)
{
	if((a[2] | S[i]) == a[2])
	{
		int si = S[i];
		vis[2][S[i]] = 1;
		for(int j = 0;j <= tot;j++)	
		{
			int sj = S[j];	
			if(!vis[1][sj]) continue;
			if((si & sj) == 0)
				dp[2][si][sj] = max(dp[2][si][sj],dp[1][sj][0] + num[si]);	
		}
	}
}//第二行
for(int r = 3;r <= n;r++)
{
	for(int i = 0;i <= tot;i++)//第r行状态
	{
		int si = S[i];
		if((a[r] | si) == a[r])
		{
			vis[r][si] = 1;
			for(int j = 0;j <= tot;j++)//第r-1行状态
			{
				int sj = S[j];
				if(!vis[r - 1][sj]) continue;
				if(si & sj) continue;
				for(int k = 0;k <= tot;k++)//第r-2行状态
				{
					int sk = S[k];
					if(!vis[r - 2][sk]) continue;
					if(((sj & sk) | (si & sk)) == 0)
							dp[r][si][sj] = max(dp[r][si][sj],dp[r - 1][sj][sk] + num[si]);
				}
			}
		}
	}
}
int ans = -1;
for(int i = 1;i <= tot;i++)
	for(int j = 1;j <= tot;j++)
		ans =  max(ans,dp[n][S[i]][S[j]]);//遍历所有情况
  • \(Tip:\)为了避免内存危机，可以定义\(dp_{i,j,k}\)为当前为第\(i\)行，该行状态是合法状态中的第\(j\)个，上一行是合法状态中的第\(k\)个

把代码中的\(si,sj,sk\)改成\(i,j,k\)就行

2831 [NOIP2016 提高组] 愤怒的小鸟

click

写这题前趴电脑前面睡了半个小时，可能是被状压NaOH的昏迷了

\(n\leqslant 18\)，考虑用\(0,1\)表示猪的死活，\(0\)表示没死，\(1\)表示死了

设\(dp_{S}\)表示达到状态\(S\)所需的最少鸟数

那么

\[dp_S=\min{(dp_{S'}+num_{S'})} \]

显然，死的猪复活不了，所以\(S'\)中\(1\)的个数在\(S\)的基础上要多，设多出来\(k\)个\(1\)，那么\(num_{S'}\)就表示打死那\(k\)只猪所需的最少鸟数

更具体的，由于抛物线的形式，所以两个点就能确定一个抛物线，那么设\(P_{i,j}\)表示经过第\(i,j\)个点能杀死的猪的集合，和\(S\)相同，杀死的猪在\(P_{i,j}\)中对应的数位为\(1\)

那么

\[dp_{S|P_{i,j}} = \min(dp_S+1) \]

但也可能存在需要额外消耗一只鸟（说明过这个点的抛物线上只有一个点\(k\)）的情况，还得再处理一下

\[dp_{S|(1<<(k-1))} = \min(dp_S+ 1) \]

接下来考虑一些细节

  • 求\(P_{i,j}\)

设\((x_1,y_1),(x_2,y_2)\)在同一条抛物线上，那么

\[\begin{cases} ax_1^2+bx_1 = y_1\\ ax_2^2+bx_2 = y_2 \end{cases} \]

解得

\[ a=\large\frac{y_1x_2-y_2x_1}{x_1x_2(x_1-x_2)}, b = \large\frac{y_1x_2^2-y_2x_1^2}{x_1x_2(x_2-x_1)}\]

int init(int p,int q)
{
	double x1 = point[p].x,x2 = point[q].x;
	double y1 = point[p].y,y2 = point[q].y;
	if(x1 == x2) return 0;//会导致a变成nan
	double a = (y1 * x2 - y2 * x1) / (x1 * x2 * x1 - x1 * x2 * x2);
	double b = (y1 * x2 * x2 - y2 * x1 * x1) / (x1 * x2 * x2 - x1 * x2 * x1);
	//cout << a << endl;
	if(a >= 0) return 0;//题目要求
	int s = 0;
	for(int i = 1;i <= n;i++)
	{
		double x = point[i].x,y = point[i].y;
		if(fabs(a * x * x + b * x - y) < eps)//实数误差在允许范围内
		{
			s |= 1 << (i - 1);
			dp[s] = dp[1 << (i - 1)] = 1;//当前的猪和目前找到的在一条线上的猪都能用一只鸟打掉
		}
	}
	return s;
}
  • 跳过不必要的枚举

我们需要一个\(i\)来枚举状态，需要\(j,k\)枚举\(P_{j,k}\)，总复杂度是\(O(Tn^2\times(2^n-1))\)，极限\(2e9,\)可能会超时（这么说是因为不加此处的优化好像也能过）

显然，使用\(P_{j,k}\)的前提就是第\(j,k\)只猪都活着，所以得保证当前\(i\)的第\(j,k\)位均为\(1\)

for(int i = 0;i <= (1 << n) - 1;i++)
{
	for(int j = 1;j <= n;j++)
	{
		if((i >> (j - 1)) & 1 == 1) continue; //第j只猪是活的
		for(int k = 1;k <= j;k++)
		{
			if((i >> (k - 1)) & 1 == 1) continue;//第k只猪是活的
			dp[i | S[j][k]] = min(dp[i | S[j][k]],dp[i] + 1);
		}
		dp[i | (1 << (j - 1))] = min(dp[i | (1 << (j - 1))],dp[i] + 1);
	}
}

我才不说那个把\(double\)老写成\(int\)的傻子是谁 （我）

P4163 [SCOI2007] 排列

click

\(|s| \leqslant 10\)，状压字符串

用\(01\)表示某一位数字有没有被使用，\(0\)表示没用，\(1\)表示用了

接下来定义\(dp\)状态

发现“整除”这个东西挺不好保证的，尤其是在只知道位的情况下更不好办了

为了解决这个问题，不妨引进余数，整除就是余数为\(0\)的情况

故设\(dp_{S,d}\)表示状态为\(S\)，余数为\(d\)时的方案数

如果要使用第\(i\)个数，那么根据\(dp\)尿性，前\(i-1\)位已经排好（但具体数字可能不是前\(i-1\)个数），应当放到第\(i\)位（从右往左），那么由余数可加性可得新余数就是\((10\times j + s_i) \% d\)，其中\(j\)就是前 \(i-1\)位模\(d\)的余数

所以得到方程

\[dp_{S|(1<<(i-1)),(10\times j+s_i) \% d} = \sum_{0\leqslant j \leqslant d-1}dp_{S,j} \]

\[ans = dp_{(1 << |s|)-1,0} \]

由上一道题可知第\(i\)位必须是\(0\)

坑点：需要对序列去重，或者打标记防重复

if(vis[c[j] - '0']) continue;//该数字已被使用
if(i & (1 << (j - 1))) continue;//第j位被用了
vis[c[j] - '0'] = 1;//打标记

P2167 [SDOI2009] Bill的挑战

click

\(N \leqslant 15\)，状压每个字符串是否与\(T\)匹配，\(1\)表示配上了，\(0\)表示没配上

很明显，状态中最多只能有\(K\)个\(1\)

但有些\(S\)是一定不能同时匹配上一个\(T\)的，可以预处理

接下来就是定义\(dp\)状态

\(dp\)中至少有一维是\(S\)，考虑另一位放什么

由于每一位放不同的字母会产生不同的效果，所以考虑用一维枚举放到了第几位

所以得到\(dp_{i,S}\)表示当前在第\(i\)位，匹配状态为\(S\)的方案数

答案就是

\[\sum_{num(S)=K}dp_{n,S} \]

\[num(S)表示S中1的个数 \]

方程就是

\[dp_{i,S} += dp_{i-1,S'} \]

\[其中S'在第i位放上某一字符时可以转化为S \]

接下来细嗦预处理并具体化\(dp\)

设\(vis_{i,j}(1\leqslant j \leqslant 26)\)表示第\(i\)位放了第\(j\)个字符时仅第\(i\)列的匹配情况（\(01\)表示）

for(int i = 1;i <= l;i++)
{
	for(int j = 1;j <= 26;j++)
	{
		for(int k = 1;k <= n;k++)
		{
			char op = s[k][i];
			if(op == '?') vis[i][j] |= (1 << (k - 1));
			else
			{
				if(op - 'a' + 1 == j) vis[i][j] |= (1 << (k - 1));
				else continue;
			}
		}
	}
}

那么结合\(dp\)可得

\[dp_{i,S\&vis[i][j]} += dp_{i-1,S} \]

按位与就表示只有前\(i-1\)位配上了(\(S\)对应位为\(1\))并且第\(i\)位也能配上（\(vis[i][j]\)对应位为\(1\)）该串状态才可能为\(1\)

初始化：\(dp_{0,2^n-1} = 1\)

dp[0][(1 << n) - 1] = 1;
for(int i = 1;i <= l;i++)
	for(int s = 0;s <= (1 << n) - 1;s++)
			for(int j = 1;j <= 26;j++)
				dp[i][s & vis[i][j]] = (dp[i][s & vis[i][j]] + dp[i - 1][s]) % mod;

听说还有容斥做法，。先咕咕

Disease Management

click

好像比前面都裸

把每头牛的得病状态压缩，类似上面的方程，把与改成或就行

坑点：二维要先继承上一维的状态再\(dp\)

for(int i = 1;i <= n;i++)
{
	for(int s = 0;s <= (1 << d) - 1;s++)
	{
		dp[i][s] = dp[i - 1][s];//先继承
		dp[i][s | a[i]] = max(dp[i][s | a[i]],dp[i - 1][s] + 1);
	}
}

标签：表示,状态,int,状压,x2,x1,dp
From： https://www.cnblogs.com/MLP123/p/18041790

相关文章

  • Windows如何检测UDP端口的连通性
    在Windows平台上如何检测UDP端口的连通性呢？其实，平时我们遇到检测TCP端口的连通性的情况比较多，遇到检测UDP端口连通性的情况较少。而且检测UDP端口的连通性比较复杂一点。像检测TCP端口是否连通（放开），Windows平台，一般常用的工具有telnet、psping等工具，而检测UDP端口的工具，在Linux平台......
  • dp练习
    合并类len=2,[k]消消乐类，len=3,[i+1][j-1]else[k]Bracketshttps://vjudge.net/problem/POJ-2955#include<iostream>#include<cstring>usingnamespacestd;intdp[101][101];boolflag=1;boolpei(inti,intj,chara[]){if(a[i]=='('&&......
  • 基于STM32F407MAC与DP83848实现以太网通讯四（STM32F407MAC数据收发与DMA描述符）
    上一章实现的MAC数据包的基础收发功能，但是只是简单的操作了ETH外设的收发包函数并没有深入了解其中的原理逻辑，本章结合STM32F40x文档与STM32F4x7_ETH_Driver驱动库了解MAC的收发包流程。一、描述符列表 在创建描述符列表之前先了解描述符列表的定义，描述符就软件来说就是一个结......
  • CF932F Escape Through Leaf【DP，李超线段树】
    有一颗\(n\)个节点的树，根节点为\(1\)。每个节点有两个权值，第\(i\)个节点的权值为\(a_i,b_i\)。你可以从一个节点跳到它的子树内任意一个节点上。从节点\(x\)跳到节点\(y\)一次的花费为\(a_x\timesb_y\)。跳跃多次走过一条路径的总费用为每次跳跃的费用之和。求每个节......
  • P8935 [JRKSJ R7] 茎【DP】
    给定一棵\(n\)个点的根节点为\(1\)的有根树，现在你要对这棵树进行剪枝，每次你可以选择一个还未被剪掉的节点\(u\)进行操作，然后剪掉\(u\)的子树所有点（包括\(u\)）。当且仅当你剪掉\(1\)时，操作停止。再给定\(x,k\)，求有多少种不同的操作序列满足第\(k\)次恰好操作的是\(x......
  • AT_joi2015ho_b （dp思想）
    难度2比较有意思的dp题首先发现这就是将一个环从中间一点一点剥开的过程。其次观察到joi取时右端点减左端点为偶数，ioi取时为奇数，所以一次一次dp即可。看到这种题时，发现有环，就要想到双倍延长再模拟一下题意，手玩一下即可//LUOGU_RID:117752061#include<bits/stdc++.h>using......
  • ABC283E （dp思想）
    难度1这题看到一点思路也没有，但是看到最小操作数想到二分，dp和贪心，二分答案的check显然不会，贪心不会。发现对于一行，前面的\(i-2\)是不会影响的，这一行也不会影响后面的\(i+2\)行，所以是dp。考虑如何设计状态因为\(i-1\)和\(i+1\)行都会影响，所以设计出来一个dp[i][0/1][0/1][0/1]的东......
  • P10156（dp思想）
    难度2也是比较有意思的一道题。首先发现每个小团体独立，所以对于每个小团体分开直接暴力dp，dp[i][j]表示当前小团体做到第i人，走了j人，然后O(n)转移，加上部分分喜提50pts。为什么要O(n)转移呢，因为我要枚举匹配的两个人然后算贡献。但是对于这种带绝对值的贡献，我们一般都要把绝对值拆掉......
  • P1240+P1350+ AT_abc282_g得出的一些dp技巧
    在遇到一些题目在设状态时，前面的状态对后面的有影响，比如在P1240和P1350中前面的放置会对后面的有影响，正常的状态是不行的。以前可能考虑状态压缩，但现在我们可以通过发现前面状态的一些共性，比如在P1240+P1350中前面放了k个車那么一定有k行被占用，所以就不用记录之前那些行被占用了。......
  • 【学习笔记】树型DP学习笔记
    学习笔记索引省流：被吊打了自己开的一个坑，死也要填完它。希望我随手写下的笔记对您的学习有所帮助（也不太可能）。更改日志2024/01/08：开坑，写了树的直径和换根DP，写不动了（（（2024/01/08晚上：更新了最小点覆盖和最大独立集，看来精神还可以，顶着明天做手术的风险2024/01/09：修改错误+增补......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99