直播间 网站建设,大理州城乡建设局官方网站,网站建设开发合同模板下载,网站建设与维护的软件状压dp#xff1a;意思是将状态进行压缩#xff0c;从而更容易地写出状态转移方程
通常做法#xff1a;将每个状态#xff08;一个集合#xff09;用二进制表示#xff0c;每个位的1就代表着这个编号的元素存在#xff0c;0就代表着这个编号的元素不存在#xff0c;如…状压dp意思是将状态进行压缩从而更容易地写出状态转移方程
通常做法将每个状态一个集合用二进制表示每个位的1就代表着这个编号的元素存在0就代表着这个编号的元素不存在如二进制100110即是集合{1,2,5}的压缩
通过状态压缩我们可以使得状态通过位运算来判断是否可以转移
如
一、
假设棋盘要放置k个国王国王对其周围八个格子都可发动进攻如果要求这一行与上一行的国王不能相互进攻
那么设上一行的状态为x二进制数这一行的状态为y的话由于这一行放的国王的左上角正上方右上角都不能出现上一行的国王
所以
正上方不出现上一行的国王的条件为xyfalse
左上角不出现上一行的国王的条件为x(y1)false
右上角不出现上一行的国王的条件为x(y1)false
通过简单的位运算判断对于每一个y我们都可以枚举所有x并可以快速找出能够转移到y的合法的x的状态从而使状态转移变得简单
因此对于这种题目我们通常需要预处理出所有的x状态以方便我们进行枚举
题目链接#2153. 「SCOI2005」互不侵犯 - 题目 - LibreOJ (loj.ac)
实现代码
#include cstdio
#include iostream
#include cstring
using namespace std;
int n,K;
int sti[600],sta[600],cnt;
//sti[i]第i种状态压缩
//sta[i]: 第i种状态放的国王的数量
//cnt:状态总数
long long f[10][85][600];
//状态转移方程
//f[i][l][j]:摆到第i行已经摆了l个而且第i行的摆法是j状态总共有多少种方法数
//所以:
//f[i][l][j]sigma f[i-1][l-sta[j]][x] 枚举所有合法的x//预处理所有状态
void dfs(int x,int num,int cur){if(curn){sti[cnt]x;sta[cnt]num;return;}dfs(x|(1cur),num1,cur2);//cur所指的位置放棋子那么由于国王会进攻隔壁的棋子所以cur2才是到下一个能放棋子的位置dfs(x,num,cur1);//cur所指的位置不放棋子则遍历到下一个位置即可
}
int main(){cinnK;dfs(0,0,0);//先初始化第一行for(int i1;icnt;i) f[1][sta[i]][i]1;for(int i2;in;i)//遍历到第i行for(int j1;jcnt;j)//第i行以第j种状态存在for(int kK;ksta[j];k--)//枚举棋盘上已经摆了k个棋子for(int x1;xcnt;x)//枚举上一行所有要转移的状态xif(!(sti[j]sti[x])!((sti[j]1)sti[x])!((sti[j]1)sti[x]))//判断是否合法f[i][k][j]f[i-1][k-sta[j]][x];long long sum0;for(int j1;jcnt;j)sumf[n][K][j];coutsum;return 0;
}
两道练习题
1.#10173. 「一本通 5.4 练习 2」炮兵阵地 - 题目 - LibreOJ (loj.ac)
实现代码
#include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;
int n,m,cnt;
int sti[2100],sta[2100];
//滚动数组
int f[2][2100][2100];
//预处理行
char s[100];
void dfs(int x,int num,int cur){if(curm){sti[cnt]x;sta[cnt]num;return;}dfs(x|(1cur),num1,cur3);dfs(x,num,cur1);
}
int board[110];
int main(){cinnm;for(int i1;in;i){scanf(%s,s);for(int j0;jm;j) if(s[j]H) board[i]|(1j);}dfs(0,0,0);for(int i1;icnt;i) if(!(sti[i]board[2])) for(int j1;jcnt;j) if(!(sti[j]board[1])!(sti[i]sti[j])) f[0][i][j]sta[i]sta[j];for(int i3;in;i)for(int j1;jcnt;j)for(int x1;xcnt;x){f[i%2][j][x]0;if(!(sti[j]board[i])!(sti[x]board[i-1])!(sti[j]sti[x]))for(int k1;kcnt;k)if(!(sti[k]board[i-2])!(sti[j]sti[k])!(sti[x]sti[k]))f[i%2][j][x]max(f[i%2][j][x],f[(i%2)^1][x][k]sta[j]);}int ans 0;if(n1){for(int i1;icnt;i)if(!(board[1]sti[i]))ansmax(ans,sta[i]);coutans;return 0;}for(int i1;icnt;i)for(int j1;jcnt;j)ansmax(ans,f[n%2][i][j]);coutans;return 0;
}
2.P1879 [USACO06NOV] Corn Fields G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
实现代码
#include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;
int n, m;
const int N 5E3 10;
int cnt;
int board[13];
int sti[N];
long long f[13][N]; // f[i][j]到了第i行第i行为第j种状态的草坪
int mod 1E8;
// 转移方程
// f[i][j]sigma f[i-1][x]
void dfs(int x, int cur)
{if (cur n){sti[cnt] x;return;}dfs(x | (1 cur), cur 2);dfs(x, cur 1);
}
int main()
{cin m n;for (int i 1; i m; i){for (int j 0, k; j n; j){scanf(%d, k);board[i] | ((k ^ 1) j);}}dfs(0, 0);for (int i 1; i cnt; i)if (!(sti[i] board[1]))f[1][i] 1;for (int i 2; i m; i)for (int j 1; j cnt; j)for (int x 1; x cnt; x)if (!(sti[j] sti[x]) !(sti[j] board[i]))f[i][j] (f[i][j] f[i - 1][x]) % mod;long long ans 0;for (int i 1; i cnt; i)ans (ans f[m][i]) % mod;cout ans;return 0;
}
二、
集合问题
上文提到用二进制对应位置的1可表示该编号的元素存在于集合中那么每一个二进制数就可以代表一个状态压缩的集合
我们先来熟悉以下几种位运算操作
1.对于一个数x而言x-1的二进制表达与x的区别在于x-1将x的最低位的1变为了0且这个1往后的更低位的0全都变为了1
那么如果我们进行x(x-1)的操作以x最低位的1为分界点其往低位包括其自身都将变为0而其更高位的x所对应的1保持不变也就是说如果我们进行x(x-1)而得到的新的二进制数实际上是把x的最低位的1变为0其他保持不变所得到的新的二进制数
2.对于一个数而言如果他是2的非负整数幂它的二进制表达中一定只有一个1且会在某个位置
由上述的x(x-1)的操作我们可知如果x是2的非负整数幂那么一定有x(x-1)0
3.对于一个数x所代表的集合而言 我们可通过消除其二进制表达的若干个1从而得到他的全部子集实现代码如下
for(int sm;s;s(s-1)m){
}
每进行一次迭代都会得到一个ss为m的一个非空子集的状态压缩
4.遍历元素个数为n的集合的子集的子集
实现代码如下
for(int m0;m(1n);m){//第一个for遍历元素为n的集合的子集for(int sm;s;s(s-1)m){//第二个for遍历子集的子集}
}
该操作的时间复杂度为证明略
5.求集合a对全集u的补集b
则ba^u
6.求集合a对全集u的交集b
则bau
7.求集合a对全集u的并集b
则ba|u 例题
P5911 [POI2004] PRZ - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
实现代码
#include cstdio
#include iostream
#include cstring
#include algorithm
using namespace std;
int W,n;
int t[20],w[20],tim[70000];
const int INF(130);
//总共16个人
//记录所有合法子集的状态
//那么dp[i]表示状态为i的情况下所用时的最短时间
//最后一定是求状态为全满的的dp值
//那么转移方程为
//dp[i]min(dp[a]dp[b]),其中a|bi
//也就是说a是i的全部子集
//那么b就是a对于i的补集
void check(int tmp,int total,int cost){for (int i 0; i n; i){if ((tmp i) 1){cost min(cost, t[i]);total w[i];}if(totalW) return;}tim[tmp]cost;
}
int main(){cinWn;for(int i0;in;i) cint[i]w[i];int N(1n)-1;for(int mN;m;m(m-1)N){tim[m]INF;check(m,0,INF);}for(int m0;m(1n);m)for(int sm;s;s(s-1)m)tim[m]min(tim[m],tim[s]tim[m^s]);couttim[N];return 0;
}
