1215: 愚蠢的摄影师（C语言）（主要提供思路，代码并不难）

解题思路:

对于只有一个人的情况，自然只有一种

对于两个人也是一种

三个人为两种

1-->1

2-->1

3-->2

对于四个人的情况我们可以分为种

一、第一个第二个分别为  （1,2）这是对于后面的排序相当于三个人的时候排完第一个之后对后面进行排序

二、第一个第二个分别为  （1,3）

        这时第三个可以为2或4

        壹、第三个为2：（1,3,2）剩下的相当于对（4-3）种情况下排序的结果

        贰、第三个为4：（1,3,4）这时第四个必须为2（1,3,4,2）                

对于n个人的情况我们可以分为种

一、第一个第二个分别为  （1,2）这是对于后面的排序相当于n-1个人的时候排完第一个之后对后面进行排序，情况数为第n-1个的结果数

二、第一个第二个分别为  （1,3）

        这时第三个可以为2或4或5

        壹、第三个为2：（1,3,2） 剩下的相当于对（n-3）种排序的结果

        贰、当n>=5之后第四个为4会失败

        叁、当第四个取5的时候只会有一种情况（整个数据先以2为差的等差数列上升，上升到最大再以2为差下降，）

                （例：（1,3,5,7,8,6,4,2）  （1,3,5,7,9,11,10,8,6,4,2））

所以对于n>3的情况可以总结出来公式

ans[n]=ans[n-3]+ans[n-1]+1;

                

注意事项:

参考代码:

#include<stdio.h>

int main()

{

    int N,i;

    int ans[55]={0};

    ans[0]=1;

    ans[1]=1;

    ans[2]=2;

    for(i=3;i<55;i++)

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

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

    printf("%d\n",ans[N-1]);

    return 0;

}