最初的第一印象是和组合数一个性质的题目。所以用了回溯法，结果，你懂的。。。

#include<stdio.h>

#include<math.h>

void dfs(int n,int d,int num[]);

int k=0;

int max=0;

int main(){

	while(scanf("%d",&k)!=EOF){

		int num[57]={0};

		num[1]=1;

		dfs(1,1,num);

		printf("%d\n",max);

		max=0;

	}

	return 0;

}

void dfs(int n,int d,int num[]){

	int m;

	if(n==k){

		max++;

		return ;}

	for(m=1;m<=k;m++){

		if((!num[m])&&((fabs(m-d))<=2)){

			num[m]=n+1;

			dfs(n+1,m,num);

			num[m]=0;

		}

	}

}

结果看完解题报告，原来是斐波那契数列。。。。

#include <stdio.h>

int main()

{

    int i,f[60],n;

    f[1]=f[2]=1;

	f[3]=2;

    for(i=4;i<56;i++){

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

    }

    while(scanf("%d",&n)!=EOF){

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

		}

    return 0;

}

各种纠结，不过，开心的是，我居然用搜索写出来了，虽然没过，但是也是有进步的啦