posts - 2,  comments - 3,  trackbacks - 0
http://acm.timus.ru/problem.aspx?space=1&num=1260

思路:假设F[n]表示n个数的满足题意的合法排列数,那么F[n] = F[n - 1] + F[n -3] + 1;
         F[n - 1] 是这样来的:F[n],1排第一,第2个位置只能排2,3. 假设第2个位置排2 那么序列就是12..... = 1, (2....)序列。2.... =  F[n - 1];
         F[n - 3] + 1 是这样来的:F[n],1排第一,第2个位置只能排2,3. 假设第2个位置排3 那么序列就是13 ..... = 13(....)2或者132(....)序列。
               13(....)2只能有一种,因为4只能排2前面, 5只能排3后面。。。。  就如这样:13 5764 2
               132(....)  = 132(4......),(4....) = F[n-3];
Code:

#include<cstdio>

int F[56];
void init(){
   int i = 0;
   F[0] = 0;
   F[1] = 1;
   F[2] = 1;
   for(i = 3; i <= 55; i++){
      F[i] = F[i - 1] + F[i - 3] + 1;
   }
}

int main(int argc, char* argv[], char* env[])
{
   int n = 0;
   init();
   while(scanf("%d", &n) != EOF){
      printf("%d\n", F[n]);
   }
   return 0;
}

posted on 2011-07-20 17:51 Lshain 阅读(344) 评论(0)  编辑 收藏 引用 所属分类: Algorithm题解-timus

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿

文章分类(46)

文章档案(33)

ACM

Algorithm Link

BLOG

Format analysis

Forum

Math

mirror

OpenGL

Protocol Analyzer

Recent Contests

Search

WIN32 Programming

最新随笔

搜索

  •  

最新评论

阅读排行榜

评论排行榜