poj1953 World Cup Noise [3]

(1)隔壁宿舍大佬的递归写法

/*下午上实验课，坐在一起做poj2506，然后我不会，向大佬请教。说递归然后就扯到了这个题。大佬的思路，和直接Fibonacci递归不一样。他是这样说的，因为有n位，用递归的思想，先考虑第n位，如果第n位为1，那么n-1位就必须是0，题目不允许有相邻的1存在；若第n位是0，那么第n-1位可以是1或者0。代码如下，不过超时了，未完待续。*/#include 
   
    #include 
    
     #include 
     
      using namespace std;long f(long n, long b){    if(n==1)return 1;    if(b==1)return f(n-1, 0);    if(b==0)return f(n-1, 0) + f(n-1, 1);}int main(){    long n;    while(~scanf("%d", &n))    {        for(long i=0;i
      
       >k;            cout<<"Scenario #"<
       
        <<":"<

(2)ac代码

/*大佬把递归向下推了一位，ac了。学习了，当大家都直接套Fibonacci的时候，这样也可以，以后要多跟大佬在一起，多多向大佬学习。先说下推的过程，这是原来超时的递归：long f(long n, long b){    if(n==1)return 1;    if(b==1)return f(n-1, 0);    if(b==0)return f(n-1, 0) + f(n-1, 1);}(1)if(b==1)return f(n-1, 0); -->if(b==1)return f(n-2, 0)+f(n-2, 1);因为if(b==1)return f(n-1, 0);又b==0 (f(n-1, 0)中的b)时有：if(b==0)return f(n-1, 0) + f(n-1, 1);所以f(n-1, 0) = f(n-2, 0) + f(n-2, 1);-->if(b==1)return f(n-2, 0)+f(n-2, 1);(2)同理，可推出：if(b==0)return f(n-1, 0) + f(n-1, 1);-->if(b==0)return 2*f(n-2, 0) + f(n-2, 1);代码如下：*/#include 
   
    #include 
    
     #include 
     
      using namespace std;long f(long n, long b){    if(n==1)return 1;    if(n==2&&b==1)return 1;    if(n==2&&b==0)return 2;    if(b==1)return f(n-2, 0)+f(n-2, 1);    if(b==0)return 2*f(n-2, 0) + f(n-2, 1);}int main(){    long n;    while(~scanf("%d", &n))    {        for(long i=0;i
      
       >k;            cout<<"Scenario #"<
       
        <<":"<