URAL 1260 Nudnik Photographer（递推）

题意：给你1到n这n个数，排成一排，然后1放在左边最开始，剩下的数进行排列，要求排列出来的数列必须满足任何两个相邻的数之间的差不能超过2，问你有多少种排列

思路 : 对于dp[n], n个人时求F[n]。第2个位置放2时有F[n-1]种；第2个位置放3，第3个位置放2，第4个位置只能放4，有F[n-3]种；第2个位置放3，第3个位置放5，13578642，有1种；第2个位置放3，第3个位置不能放4。

所以：

1、12……（dp[n-1]）

2、1324……（dp[n-3]）

3、1357……8642（一种确定的情况）

 //URAL 1260

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 using namespace std ;

 int dp[] ;

 void chart()

 {

     dp[] = dp[] =  ;

     dp[] =  ;

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

         dp[i] = dp[i-]+dp[i-]+ ;

 }

 int main()

 {

     int n ;

     chart() ;

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

     {

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

     }

     return  ;

 }

巴特西

URAL 1260 Nudnik Photographer（递推）

最新文章

热门文章