题目描述:

请计算长度为N且不含连续1的01串的个数。

例如,当N=3时,答案为5,因为长度为3且不含连续1的01串一共有5个:000, 001, 010, 100, 101。

输入格式:

一个整数N,表示字符串的长度。

输出格式:

一个整数,表示符合条件的01串的个数。

数据范围:

1 ≤ N ≤ 20

输入样例:

3

输出样例:

5

题目分析 一眼DFS。

代码实现:

#include <iostream>
#include <bitset>
#include <unordered_set>
using namespace std;
const int N = 30;

int n;
bitset <N> vis;
unordered_set <string> ans;
void dfs(int len, string s) {
    if (len == n) {
        ans.insert(s);
        return ;
    }
    dfs(len + 1, s + '0');
    if (*(s.end() - 1) != '1') dfs(len + 1,s + '1');
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    dfs(0, "");
    cout << ans.size();
    return 0;
}
分类: DFS

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status