“多少种”是搜索和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;
} 
蓝桥真题 文章被收录于专栏

蓝桥真题的题解

全部评论

相关推荐

有担当的灰太狼又在摸鱼:零帧起手查看图片
点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务