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 阅读(348)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm 、
题解-timus