-
这个题当时没做出来，就差一点额，今天就在DFS中加1，就过了！！
我的代码：
View Code我的做法是：就是一步一步的往下推的，可惜的是当时少推了一种情况；首先是1是必须是第一个的，是1的时候我就想着用f[1]表示；从第二个数开始，是2或3；当是2的时候，就用f[2]表示；当时3的时候，我发现如果n>4的话，第二个数为3那么第三四都固定了即必须是1324，因为只有这样才符合题意，这时我就理解为这不等于直接到4了？那我就有f[4]表示；又经过很多的推导我发现都是这个规律，所以当时就推出f[i]=f[i+1]+f[i+3];我这里的f[i]表示到第i个数的时候的所包含的各种情况！可惜我少想了一种情况，即1、3、5、7……2n+1、2n……6、4、2这种情况！即f[i]=f[i+1]+f[i+3]+1;如代码中的tmp[i]=DFS(i+1)+DFS(i+3)+1;
出题人的代码:
View Code
#include <stdio.h>
int main()
{
int i,f[60];
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;
}额，看着都是这么的牛B哈！代码简单，意义不简单啊！
f[i]=f[i-1]+f[i-3]+1;显然这个公式看着跟我推的有些相似，但却又很不同，意义很不同；它的解析是：f[i]表示有i个依次排列的数、第一个数固定、所有符合条件的排列种数。例：f[5]=f[4]+f[2]+1; 1 2 3 4 5 第一个数为1，第二个数为2时、f[4]表示：2-5共四个数、2固定的所有排列种数！第二个数为3时、f[2]时表示：（1 3 2 4固定）4-5共两个数、4固定的所用排列种数！1表示：1 3 5 4 2 即上面所说的那种情况！
还有傻傻做的方法，就不贴代码了。她是自己推出来的公式，反正与上边有很大的差异、、话说人家推导了9页才发现的规律！啊，很BT啊，哈哈！
