EOJ刷题记录第八弹

Problem #2846 - ECNU Online Judge

思路

从$dp$或者$dfs$角度考虑，$dp$比较困难，索性直接从$dfs$角度来写。调试的时候遇到了一个问题，if(fir != 1 && sec != 0)这个判断条件的作用范围是什么？我觉得直观的感受是如果第一位不为1并且第二位不为0（即10*）的情况下，下一位只能填1。在debug时候死活有一些情况被莫名其妙的剪枝掉，才考虑判断条件问题：如果前缀是00会怎么样？true&&false=false，会被剪枝，在数学符号上成立但在判断条件中就错了，最后改成更加直观，注重于整体的判断条件：if(!(fir == 1 && sec == 0))

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;
int ans;

// idx 当前下标，fir:上上一个位置，sec:上一个位置
void dfs(int idx, int fir, int sec)
{
    if(idx == n) {
//        cout << "output:" << fir << ' ' << sec <<endl;
        ans ++;
        return;
    }

//    if(fir != 1 && sec != 0)
    if(!(fir == 1 && sec == 0))
        dfs(idx + 1, sec, 1);

    dfs(idx + 1, sec, 0);
}

int main()
{

    while(cin >> n)
    {
        if(n == -1) break;
        ans = 0;
        dfs(0, -1, -1);
        cout << ans << endl;
    }

    return 0;
}