問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1953思路:
如果想通了，其實(shí)就是道挺簡(jiǎn)單的動(dòng)規(guī)題
zero_end[i]記錄第i位以0結(jié)尾的合法排列
one_end[i]記錄第i位以1結(jié)尾的合法排列
狀態(tài)方程即:
zero_end[i+1] = zero_end[i] + one_end[i]
one_end[i+1] = zero_end[i]
以深度搜索的遞歸樹(shù)即可觀察得出以上結(jié)論(*^__^*) 嘻嘻……
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 45
5 int zero_end[MAX_LEN+1];
6 int one_end[MAX_LEN+1];
7
8 int
9 build_table()
10 {
11 int i;
12 zero_end[1] = 1;
13 one_end[1] = 1;
14 for(i=2; i<=45; i++) {
15 zero_end[i] = zero_end[i-1] + one_end[i-1];
16 one_end[i] = zero_end[i-1];
17 }
18 }
19
20 int
21 main(int argc, char **argv)
22 {
23 int i, n, tests;
24 build_table();
25 scanf("%d", &tests);
26 for(i=1; i<=tests; i++) {
27 scanf("%d", &n);
28 printf("Scenario #%d:\n%d\n\n", i, zero_end[n]+one_end[n]);
29 }
30 }