nyoj——469 擅長排列的小明 II

擅長排列的小明 II

時間限制： 1000 ms  |  記憶體限制： 65535 KB 難度： 3

描述

小明十分聰明，而且十分擅長排列計算。

有一天小明心血來潮想考考你，他給了你一個正整數n，序列1,2,3,4,5......n滿足以下情況的排列：

1、第一個數必須是1

2、相鄰兩個數之差不大于2

你的任務是給出排列的種數。

輸入

多組資料。每組資料中輸入一個正整數n（n<=55）.

輸出

輸出種數。

樣例輸入

4      

樣例輸出

4

規律題

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<ctype.h>

#include<stdlib.h>

#include<string>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<list>

#include<queue>

#include<stack>

#include<iomanip>

#include<numeric>

#include <istream>　　　　 //基本輸入流

#include <ostream>　　　　 //基本輸出流

#include <sstream>　　　　 //基于字元串的流

#include <utility>　　　　 //STL 通用模闆類

#include <complex.h>　　 //複數處理

#include <fenv.h>　　　　//浮點環境

#include <inttypes.h>　　//整數格式轉換

#include <stdbool.h>　　 //布爾環境

#include <stdint.h>　　　//整型環境

#include <tgmath.h>　　　//通用類型數學宏

#define L(a,b,c) for(int a = b;a >= c;a --)

#define M(a,b,c) for(int a = b;a < c;a ++)

#define N(a,b) memset(a,b,sizeof(a));

const int MAX=100000000;

const int MIN=-MAX;

typedef int T;

typedef double D;

typedef char C;

using namespace std;

int main()

{

    int n,a[100]={0,1,1,2,4};

    M(i,5,60)

    a[i]=a[i-1]+a[i-3]+1;

    while(~scanf("%d",&n))

        printf("%d\n",a[n]);

    return 0;

}

深搜的話就會逾時了

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<ctype.h>

#include<stdlib.h>

#include<string>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<list>

#include<queue>

#include<stack>

#include<iomanip>

#include<numeric>

#include <istream>　　　　 //基本輸入流

#include <ostream>　　　　 //基本輸出流

#include <sstream>　　　　 //基于字元串的流

#include <utility>　　　　 //STL 通用模闆類

#include <complex.h>　　 //複數處理

#include <fenv.h>　　　　//浮點環境

#include <inttypes.h>　　//整數格式轉換

#include <stdbool.h>　　 //布爾環境

#include <stdint.h>　　　//整型環境

#include <tgmath.h>　　　//通用類型數學宏

#define L(a,b,c) for(int a = b;a >= c;a --)

#define M(a,b,c) for(int a = b;a < c;a ++)

#define N(a,b) memset(a,b,sizeof(a));

const int MAX=100000000;

const int MIN=-MAX;

typedef int T;

typedef double D;

typedef char C;

using namespace std;

int a[60],b[100],n,sum;

void dfs(int num)

{

    if(num==n)

    {

        sum++;

        return ;

    }

    else

    {

        for(int i=2; i<=n; i++)

            if(!b[i]&&abs(i-a[num-1])<=2)

            {

                b[i]=1;

                a[num]=i;

                dfs(num+1);

                b[i]=0;

            }

    }

}

int main()

{

    while(cin>>n)

    {

        N(a,0)

        N(b,0)

        a[0]=1;

        sum=0;

        dfs(1);

        cout<<sum<<endl;

    }

    return 0;

}