“多少种”是搜索和dp的关键字
“多少种”是搜索和dp的关键字
本题求的是方案数,要本能的想到搜索和dp以及二进制枚举
又因为最后还要判断是否联通,有后效性,所以不能所以dp
(同等情况下,代码越长,实现的功能就越多)(dp只能求出总方案数,无法将所有状态保存,最后用来判断是否联通)
所以选用搜索,至于二进制枚举(还不太熟练)
#include<bits/stdc++.h> using namespace std; int cnt; int e[12][12],turn[10],f[10]; void init(){ e[1][2]=1;e[1][6]=1; e[2][1]=1;e[2][3]=1;e[2][7]=1; e[3][2]=1;e[3][4]=1;e[3][7]=1; e[4][3]=1;e[4][5]=1; e[6][5]=1;e[6][1]=1;e[6][7]=1; e[7][6]=e[7][5]=e[7][3]=e[7][2]=1; } int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } void merge(int x,int y){ f[find(x)]=find(y); } int pan(){ for(int i=1;i<=7;++i) f[i]=i; for(int i=1;i<=7;++i){ for(int j=1;j<=7;++j){ if(e[i][j]&&turn[i]&&turn[j]){ if(find(i)!=find(j)) merge(i,j); } } } int z=0; for(int i=1;i<=7;++i){ if(turn[i]&&find(i)==i) z++; } return z==1; } void dfs(int x){ if(x>=8) { if(pan()) cnt++; return ; } turn[x]=1; dfs(x+1); turn[x]=0; dfs(x+1); } int main(){ init(); dfs(1); cout << cnt; return 0; }
蓝桥真题 文章被收录于专栏
蓝桥真题的题解