devbox
oprspq
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

插头dp。_插头dp csdn

作者：oprspq | 2024-01-31 15:03:20

赞

踩

插头dp csdn

插头dp解决网格问题

轮廓线

就是格子的边

每次维护一个格子周围的状态，使之能够不重不漏的表示所有格子的状态

吃树


 

题意：求若干回路覆盖所有格子的方案数

枚举每个格子，维护包围着一个格子的轮廓线

对于每一行，已经处理过的格子轮廓线是格子的底边，要处理的格子由一条向左和向下（左边和顶边）的轮廓线包含，其他未处理的格子的轮廓线就是格子的顶边

就是这样

二进制压位，用1表示这条轮廓线有连向此点的边，0表示没有

分类讨论一个格子左方和上方有没有边与这个格子连接进行转移：

若这个格子是障碍，左方和上方都不能有边连接

对于其他情况：

若左上方都无，那么此格子是一条轮廓线的开端，像右下方连边（本格子更新完后，这个格子左上方的轮廓线变到了右下方，编号是下边的等于原来左边的，右边的等于原来上边的）

若只有左边有或只有下边有，连上后对下边或右边连边

若左上方都有，那么此格为一条轮廓线结束格子，不能往其他方向连边

  1. for(int S=0;S<(1<<b+1);S++){//i是行，j是列
  2. 	int l=((S>>j)&1),u=((S>>j+1)&1);
  3. 	int nS=S;
  4. 	if(nS&(1<<j)) nS^=(1<<j);
  5. 	if(nS&(1<<j+1)) nS^=(1<<j+1);
  6. 	if(!mp){
  7. 		if(!l&&!u) dp[nS]+=ty[S];
  8. 	}else{
  9. 		if(!l&&!u){
  10. 			if(i<a&&j<b-1) dp[nS|(1<<j)|(1<<j+1)]+=ty[S];
  11. 		} 
  12. 		if((!l&&u)||(l&&!u)){
  13. 			if(i<a) dp[nS|(1<<j)]+=ty[S];
  14. 			if(j<b-1) dp[nS|(1<<j+1)]+=ty[S];
  15. 		}
  16. 		if(l&&u) dp[nS]+=ty[S];
  17. 	}

这是转移，如果每一行结束后，需要让最左边的那条轮廓线转移到最右边，其他的轮廓线都右移一位

  1. memcpy(ty,dp,sizeof(ty));
  2. for(int S=0;S<(1<<b+1);S++) dp[S]=((S&1)?0:ty[S>>1]);//一开始右边轮廓线是0，最后左边轮廓线也是0

骨牌覆盖

用1*2的骨牌覆盖完一个棋盘的方案数

还是维护轮廓线，将起点终点分类讨论，每个起点可以向右或向下连边

  1.     for(int i=1;i<=a;i++){
  2. 			memcpy(ty,dp,sizeof(ty));memset(dp,0,sizeof(dp));
  3. 			for(int S=0;S<(1<<b);S++) dp[S<<1]=ty[S];
  4. 			for(int j=0;j<b;j++){
  5. 				memcpy(ty,dp,sizeof(ty));memset(dp,0,sizeof(dp));
  6. 				for(int S=0;S<(1<<b+1);S++){
  7. 					int nS=S;
  8. 					if(nS&(1<<j)) nS^=(1<<j);
  9. 					if(nS&(1<<j+1)) nS^=(1<<j+1); 
  10. 					bool l=(S>>j)&1,u=(S>>j+1)&1;
  11. 					if(l&&u) continue;
  12. 					if((l&&!u)||(!l&&u)) dp[nS]+=ty[S];
  13. 					if(!l&&!u) dp[nS|(1<<j)]+=ty[S],dp[nS|(1<<j+1)]+=ty[S];
  14. 				}
  15. 			}
  16. 		}

 白金元首与莫斯科

与刚才的题一样，发现要多次处理把一个格子变成障碍的方案数

直接枚举暴力时间复杂度受不了

再反着做一遍轮廓线

对于一个有障碍的格子，上下左右都不能有边，其他位置的连接应该一一对应，就能够使两种状态的轮廓线拼接成合法的情况

求轮廓线的大同小异，给出拼接的方式

  1. 	for(int i=1;i<=a;i++){
  2. 		for(int j=1;j<=b;j++){
  3. 			ll ans=0;
  4. 			if(mp[i][j]){
  5. 				printf("0 ");continue;
  6. 			}
  7. 			for(int S=0;S<(1<<b+1);S++){
  8. 				if(!((S>>j-1)&3)) ans=(ans+1ll*dp[i][j-1][S]*f[i][j+1][S]%mod)%mod;
  9. 			}//dp是正着的，第j-1位是左边轮廓线第j位是上边，f的第j-1位是下边第j位是右边
  10. 			printf("%lld ",ans);
  11. 		}putchar('\n');

[ZJOI2009]多米诺骨牌

要求任何一行和一列间都有骨牌连接

直接把这个限制也压进去时间复杂度肯定受不了

计算出来一个w[x][y][xx][yy]数组,表示是在这个范围的矩形中随便放置骨牌的方案数

看起来要枚举这个矩形的四个端点，其实枚举三个即可

枚举x,y,yy然后从x做到底边，得到w[x][y][x~a][y]

  1. void get_ans(int _x,int _y,int _yy){
  2. 	int x=a-_x+1,y=_yy-_y+1;
  3. 	memset(mp,0,sizeof(mp)); 
  4. 	for(int i=1;i<=x;i++){
  5. 		for(int j=1;j<=y;j++) mp[i][j]=tu[_x+i-1][_y+j-1];
  6. 	}//将矩形抠出来
  7. 	for(int i=0;i<(1<<y+1);i++) dp[i]=0;
  8. 	dp[0]=1;
  9. 	for(int i=1;i<=x;i++){
  10. 		if(i!=1){
  11. 			for(int S=(1<<y+1)-1;S>=0;S--) dp[S]=((S&1)?0:dp[S>>1]);
  12. 		}
  13. 		for(int j=1;j<=y;j++){
  14. 			for(int S=0;S<(1<<y+1);S++) ty[S]=dp[S],dp[S]=0;
  15. 			for(int S=0;S<(1<<y+1);S++){
  16. 				int l=get(S,j-1),u=get(S,j);
  17. 				int nS=S-l*(1<<j-1)-u*(1<<j);
  18. 				if(mp[i][j]=='x'){
  19. 					if(!l&&!u) dp[nS]=(dp[nS]+ty[S])%mod;
  20. 					continue;
  21. 				}
  22. 				if(!l&&!u){
  23. 					dp[nS|(1<<j-1)]=(dp[nS|(1<<j-1)]+ty[S])%mod;
  24. 					dp[nS|(1<<j)]=(dp[nS|(1<<j)]+ty[S])%mod;
  25. 					dp[nS]=(dp[nS]+ty[S])%mod;//可以不放
  26. 				}
  27. 				if((l&&!u)||(!l&&u)) dp[nS]=(dp[nS]+ty[S])%mod;
  28. 			}
  29. 		}
  30. 		w[_x][_y][_x+i-1][_yy]=dp[0];
  31. 	}
  32. }

然后考虑容斥

枚举每行之间的分割情况，然后再计算在这种情况下有多少种情况

令h[k]表示在每一行这样分割的情况下分割到第k列的情况总数

h[k]=val(0,k,S)-\sum_{j=1}^{k-1} h[j-1]*val(j,k,S)

S表示每行分割的情况

这个式子表示所有情况减去强制有分割的情况

然后再直接对于每行的情况容斥即可

  1. 	for(int S=0;S<(1<<a-1);S++){
  2. 		memset(h,0,sizeof(h));h[0]=-1;
  3. 		for(int i=1;i<=b;i++){
  4. 			for(int j=0;j<i;j++) h[i]=(h[i]-1ll*h[j]*val(j+1,i,S)%mod)%mod;
  5. 		}
  6. 		if(popcnt[S]&1) ans=(ans-h[b]+mod)%mod;
  7. 		else ans=(ans+h[b])%mod;
  8. 	}

 插头dp

发现刚才的所有情况轮廓线的状态只需用01表示，但是加上一些限制后就会使状态多种多样，我认为下面的题才算是插头dp的开始

括号序列

【模板】插头dp

多条回路变成一条回路，会有哪些变化？

1.需要将两条相邻的边合并

2.只有在结束位置才能结束一条轮廓线

然后发现只用01表示不行，因为这题需要知道哪个插头与哪个插头是联通的

引入括号序列：

0表示没有，1表示左括号，2表示右括号

1.左括号与右括号成对出现

2.在网格图上，一对匹配的左右括号中间的括号一定是匹配上的（因为如果不匹配，两条路径一定交叉，就不联通了）

因为二进制运算快，所以用4进制表示3进制

unorderer_map实测这道题会超时（可能我常数大），所以手写哈希表

推荐一种和机房大佬讨论出来的（其实完全是他看着别人的哈希表魔改的），实测开完O2非常快

  1. struct Hash_table{
  2. 	vector<pair<int,ll> >to[mod+10];
  3. 	void init(){
  4. 		for(int i=0;i<mod;i++) to[i].clear(); 
  5. 	}
  6. 	ll &operator [] (const int &S){
  7. 		int id=S%mod;
  8. 		for(int i=0;i<to[id].size();i++){
  9. 			if(to[id][i].first==S) return to[id][i].second;
  10. 		}
  11. 		to[id].push_back({S,0});
  12. 		return to[id].back().second;
  13. 	}
  14. };

也可以在记录一个数组表示状态，这样就可以遍历哈希表 

回到括号序列分类讨论

1.没有插头：若无障碍必须向下方一个左括号，向右一个右括号

2.上方和左方只有一个方向有插头：再往下方或右方推即可

3.上方和左方都是左括号：合并两个括号，找到对应的右括号，并将较靠左的改为左括号

4.上方和左方都是右括号：合并两个括号，找到对应的左括号，并将较靠左的改为右括号

5.左方右括号，右方左括号：直接合并两个括号

------3，4，5是把两条线段合并成一条线段

6.左方左括号，右方右括号：这样就是一条线段首尾相接，只能在结束位置出现，并且其他位置不能有任何括号

  1.     dp[0]=1;
  2. 	for(int i=1;i<=a;i++){
  3. 		ty=dp,dp.init();
  4. 		for(int j=0;j<s.size();j++){
  5. 			int S=s[j];
  6. 			if(S>=(1<<b*2)) break;
  7. 			dp[S<<2]=ty[S];
  8. 		}
  9. 		for(int j=0;j<b;j++){
  10. 			ty=dp,dp.init();
  11. 			for(int h=0;h<s.size();h++){
  12. 				int S=s[h];
  13. 				int l=get(S,j),u=get(S,j+1);
  14. 				int nS=S;
  15. 				if(mp[i][j]=='*'){
  16. 					if(!l&&!u) dp[nS]+=ty[S];
  17. 					continue;
  18. 				}
  19. 				nS-=get(nS,j)*(1<<j*2);
  20. 				nS-=get(nS,j+1)*(1<<(j+1)*2);
  21. 				if(!l&&!u) dp[nS|(1<<j*2)|(2<<(j+1)*2)]+=ty[S];
  22. 				if(!l&&u){
  23. 					dp[nS|(u<<j*2)]+=ty[S],dp[nS|(u<<(j+1)*2)]+=ty[S];
  24. 				}
  25. 				if(l&&!u){
  26. 					dp[nS|(l<<j*2)]+=ty[S],dp[nS|(l<<(j+1)*2)]+=ty[S];
  27. 				}
  28. 				if(l==1&&u==1){
  29. 					int h=found(nS,j+1,2);
  30. 					dp[nS-(1<<h*2)]+=ty[S];
  31. 				}
  32. 				if(l==2&&u==2){
  33. 					int h=found(nS,j,1);
  34. 					dp[nS+(1<<h*2)]+=ty[S];
  35. 				}
  36. 				if(l==1&&u==2){
  37. 					if(i==xx&&j==yy&&!nS) ans+=ty[S];
  38. 				}
  39. 				if(l==2&&u==1){
  40. 					dp[nS]+=ty[S];
  41. 				}
  42. 			}
  43. 		}
  44. 	}

 [HNOI2004]邮递员

首先这题错题，保证长宽都是偶数，因为奇数的话可能要走两点的对角线（除了1 1的hack数据）

然后就和上面那题一样了，最后答案*2（有向图）

[HNOI2007]神奇游乐园

任意一条回路，所以终点就没限制了

注意求最大值，哈希表初始值改一下

最小表示法

[JLOI2009]神秘的生物

括号表示法要求整个图所有点都要选，因为不选和消掉都是0无法判断

就要用最小表示法了

最小表示法大意是将每一种相连的连通块染上相同的颜色，让出来的颜色序列字典序最小

需要这样几个操作

  1. int get(int x,int i){
  2. 	return (x>>i*3)&7;
  3. }
  4. int cnt(int x,int i){//有几个颜色是i的
  5. 	int ans=0;
  6. 	for(int j=0;j<=a;j++) ans+=(((x>>j*3)&7)==i);
  7. 	return ans; 
  8. }
  9. int change(int S,int x,int y){//把x改成y颜色
  10. 	for(int i=0;i<=a;i++){
  11. 		if(get(S,i)==x) S=S-x*(1<<i*3)+y*(1<<i*3);
  12. 	}
  13. 	return S;
  14. }
  15. int relable(int S){//将S序列重构位最小表示
  16. 	short mp[10];
  17. 	memset(mp,0,sizeof(mp));
  18. 	int cnt=0;
  19. 	for(int i=0;i<=a;i++){
  20. 		int now=(S>>i*3)&7;
  21. 		if(!now) continue;
  22. 		if(!mp[now]) mp[now]=++cnt;
  23. 		S=S-now*(1<<i*3)+mp[now]*(1<<i*3);
  24. 	}
  25. 	return S;
  26. }

这道题维护的轮廓线是周围的一圈格子，分类讨论即可

唯一的变动在于怎么更新状态

  1. if(!l&&!u){
  2. 	dp[S]=max(dp[S],ty[S]);
  3. 	int to=relable(S|(7<<j*3)); //这个格子新建一个连通块
  4. 	dp[to]=max(dp[to],ty[S]+w[i][j]);
  5. } 
  6. if(l&&!u)  dp[S]=max(dp[S],ty[S]),dp[S|(l<<j*3)]=max(dp[S|(l<<j*3)],ty[S]+w[i][j]);
  7. if(!l&&u){
  8. 	if(cnt(S,u)>1) dp[S-u*(1<<j*3)]=max(dp[S-u*(1<<j*3)],ty[S]);
  9. 	dp[S]=max(dp[S],ty[S]+w[i][j]);
  10. }//这个格子合并到以前有的连通块
  11. if(l&&u){
  12. 	int to;
  13. 	if(cnt(S,u)>1) dp[S-u*(1<<j*3)]=max(dp[S-u*(1<<j*3)],ty[S]);
  14. 	if(u<l) to=change(S,l,u);
  15. 	else to=change(S,u,l);
  16. 	dp[to]=max(dp[to],ty[S]+w[i][j]);//将两个连通块相连
  17. }

[WC2008]游览计划

区别在于输出状态

记录每个格子的状态由上一个格子什么状态以及这一个格子什么颜色转移而来，倒推即可

自由发挥

刚才的是判断联通的两种套路方法，有些插头dp的题不需要联通这种条件，就需要自由发挥了

一般这种自由发挥的题目特点是看起来数据范围十分错误，，但是经过组合等计算后发现合法状态寥寥无几

[SCOI2011]地板

0代表没有，1代表插头还需要转弯，2表示不需要转弯

每块地板有四种长相（枚举顶点的方向），想清楚后分类讨论

  1. 	dp[0]=1;
  2. 	for(int i=1;i<=a;i++){
  3. 		ty=dp,dp.init();
  4. 		for(int h=1;h<=ty.size;h++){
  5. 			int S=ty.s[h];
  6. 			if(!((S>>b*2)&3)) dp[S<<2]=ty[S];
  7. 		}
  8. 		for(int j=1;j<=b;j++){ 
  9. 			ty=dp;dp.init();
  10. 			for(int h=1;h<=ty.size;h++){
  11. 				int S=ty.s[h];
  12. 				int l=get(S,j-1),u=get(S,j);
  13. 				int nS=S-l*(1<<(j-1)*2)-u*(1<<j*2); 
  14. 				if(mp[i][j]=='*'){
  15. 					if(!l&&!u) dp[nS]=(dp[nS]+ty[S])%mod;
  16. 					continue;
  17. 				}
  18. 				if(!l&&!u){
  19. 					dp[nS|(1<<(j-1)*2)]=(dp[nS|(1<<(j-1)*2)]+ty[S])%mod;
  20. 					dp[nS|(1<<j*2)]=(dp[nS|(1<<j*2)]+ty[S])%mod;
  21. 					dp[nS|(2<<(j-1)*2)|(2<<j*2)]=(dp[nS|(2<<(j-1)*2)|(2<<j*2)]+ty[S])%mod;//顶点靠左上
  22. 				}
  23. 				if(!l&&u==1){
  24. 					dp[nS|(1<<(j-1)*2)]=(dp[nS|(1<<(j-1)*2)]+ty[S])%mod;
  25. 					dp[nS|(2<<j*2)]=(dp[nS|(2<<j*2)]+ty[S])%mod;
  26. 				}
  27. 				if(!l&&u==2){
  28. 					dp[nS]=(dp[nS]+ty[S])%mod;//顶点靠左下
  29. 					dp[nS|(2<<(j-1)*2)]=(dp[nS|(2<<(j-1)*2)]+ty[S])%mod;
  30. 				}
  31. 				if(l==1&&!u){
  32. 					dp[nS|(2<<(j-1)*2)]=(dp[nS|(2<<(j-1)*2)]+ty[S])%mod;
  33. 					dp[nS|(1<<j*2)]=(dp[nS|(1<<j*2)]+ty[S])%mod;
  34. 				}
  35. 				if(l==1&&u==1) dp[nS]=(dp[nS]+ty[S])%mod;//顶点靠右下
  36. 				if(l==1&&u==2) continue;
  37. 				if(l==2&&!u){
  38. 					dp[nS]=(dp[nS]+ty[S])%mod;//顶点靠右上
  39. 					dp[nS|(2<<j*2)]=(dp[nS|(2<<j*2)]+ty[S])%mod;
  40. 				}
  41. 				if(l==2&&u==1) continue;
  42. 				if(l==2&&u==2) continue;
  43. 			}
  44. 		} 
  45. 	}

[CQOI2015]标识设计

再加一位表示个数，注意L只有一种长相，直接做

[NOI2010] 旅行路线

毕业题

将走的路线标号

发现除了1与a*b外，其他都与+1和-1相邻

令0为没插头，1为+1的插头，2为-1的插头

需要开两维，第一位表示插头情况，第二维是数字的情况

  1. dp[0][0]=1;
  2. 	for(int i=1;i<=a;i++){
  3. 		for(ll S=(1<<(b+1)*2)-1;S>=0;S--){
  4. 			if(ok(S)) dp[S]=(get_to(S,0)?init:dp[S>>2]);
  5. 		} 
  6. 		for(int j=1;j<=b;j++){
  7. 			for(ll S=0;S<(1<<(b+1)*2);S++) ty[S]=dp[S],dp[S].init();
  8. 			for(ll to_S=0;to_S<(1<<(b+1)*2);to_S++){
  9. 				int to_l=get_to(to_S,j-1),to_u=get_to(to_S,j);
  10. 				
  11. 				if(!ok(to_S)) continue;
  12. 				if((to_l==1&&to_u==1)||(to_l==2&&to_u==2)) continue; 
  13. 				int n_to=to_S-(to_l<<(j-1)*2)-(to_u<<j*2);
  14. 			 	for(int h=0;h<ty[to_S].size;h++){
  15. 			 		ll S=ty[to_S].s[h];
  16. 					int w=ty[to_S][S];
  17. 			 		ll num_l=get_num(S,j-1),num_u=get_num(S,j);
  18. 			 		ll nS=S-(num_u<<j*8ll);
  19. 			 		if(!to_l&&!to_u){
  20. 			 			for(ll num=2;num<a*b;num++){
  21. 			 				if(seq[num]!=mp[i][j]) continue;
  22. 			 				(dp[n_to|(1<<(j-1)*2)|(2<<j*2)][nS|(num<<j*8ll)]+=w)%=mod;
  23. 			 				(dp[n_to|(2<<(j-1)*2)|(1<<j*2)][nS|(num<<j*8ll)]+=w)%=mod;
  24. 						}
  25. 						if(i==1||i==a||j==1||j==b){
  26. 							if(seq[1]==mp[i][j]&&(i==1||i==a||j==1||j==b)) (dp[n_to|(1<<(j-1)*2)][nS|(1ll<<j*8ll)]+=w)%=mod,(dp[n_to|(1<<j*2)][nS|(1ll<<j*8ll)]+=w)%=mod;	
  27. 						}
  28. 						if(seq[a*b]==mp[i][j]) (dp[n_to|(2<<(j-1)*2)][nS|(1ll*a*b<<j*8ll)]+=w)%=mod,(dp[n_to|(2<<j*2)][nS|(1ll*a*b<<j*8ll)]+=w)%=mod;
  29. 					}
  30. 					if(to_l&&!to_u){
  31. 						ll num=num_l+(to_l==1?1:-1);
  32.                         if(num>a*b||num<=0) continue;
  33. 						if(num==1&&(i!=1&&i!=a&&j!=1&&j!=b)) continue;
  34. 						if(seq[num]!=mp[i][j]) continue;
  35. 						if(num==1||num==a*b) (dp[n_to][nS|(num<<j*8ll)]+=w)%=mod;
  36. 						else (dp[n_to|(to_l<<(j-1)*2)][nS|(num<<j*8ll)]+=w)%=mod,(dp[n_to|(to_l<<j*2)][nS|(num<<j*8ll)]+=w)%=mod;
  37. 						
  38. 					}
  39. 					if(!to_l&&to_u){
  40. 						ll num=num_u+(to_u==1?1:-1);
  41.                         if(num>a*b||num<=0) continue;
  42. 						if(num==1&&(i!=1&&i!=a&&j!=1&&j!=b)) continue;
  43. 						if(seq[num]!=mp[i][j]) continue;
  44. 						if(num==1||num==a*b) (dp[n_to][nS|(num<<j*8ll)]+=w)%=mod;
  45. 						else (dp[n_to|(to_u<<(j-1)*2)][nS|(num<<j*8ll)]+=w)%=mod,(dp[n_to|(to_u<<j*2)][nS|(num<<j*8ll)]+=w)%=mod;
  46. 						
  47. 					}
  48. 					if(to_l&&to_u){
  49. 						ll num1=num_l+(to_l==1?1:-1),num2=num_u+(to_u==1?1:-1);
  50.                         if(num1<=1||num1>=a*b||num2<=1||num2>=a*b) continue;
  51. 						if(to_u!=to_l&&num1==num2){
  52. 							if(seq[num1]!=mp[i][j]) continue;
  53. 							(dp[n_to][nS]+=w)%=mod;
  54. 						} 
  55. 					}
  56. 				}
  57. 			}
  58. 		}
  59. 	}
  60. 	ll ans=0;
  61. 	for(int i=0;i<dp[0].size;i++){
  62. 		ll S=dp[0].s[i];
  63. 		ans=(ans+dp[0][S])%mod;
  64. 	}

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号