算法训练摆动序列

问题描述

　　如果一个序列满足下面的性质，我们就将它称为摆动序列：
　　1. 序列中的所有数都是不大于k的正整数；
　　2. 序列中至少有两个数。
　　3. 序列中的数两两不相等；
　　4. 如果第i – 1个数比第i – 2个数大，则第i个数比第i – 2个数小；如果第i – 1个数比第i – 2个数小，则第i个数比第i – 2个数大。
　　比如，当k = 3时，有下面几个这样的序列：
　　1 2
　　1 3
　　2 1
　　2 1 3
　　2 3
　　2 3 1
　　3 1
　　3 2
　　一共有8种，给定k，请求出满足上面要求的序列的个数。

输入格式

　　输入包含了一个整数k。（k<=20）

输出格式

　　输出一个整数，表示满足要求的序列个数。

样例输入

样例输出

能力太渣了想不到怎么DP = =。。。dfs实现：

 1 #include<cstdio>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 int n, ans;
 6 bool mark[25];
 7 int a[25];
 8 
 9 void dfs(int top)
10 {
11     if(top>1)
12         ans++;
13     for(int i=1; i<=n; i++)
14     {
15         if(mark[i]==0)
16         {
17             if(top>1)
18             {
19                 if( (a[top-1]>a[top-2] && i<a[top-2]) || (a[top-1]<a[top-2] && i>a[top-2]) )
20                 {
21                     mark[i]=1;
22                     a[top]=i;
23                     top++;
24                     dfs(top);
25                     mark[i]=0;
26                     top--;
27                 }
28             }
29             else
30             {
31                 mark[i]=1;
32                 a[top]=i;
33                 top++;
34                 dfs(top);
35                 mark[i]=0;
36                 top--;
37             }
38         }
39     }
40 }
41 
42 int main()
43 {
44     memset(a, 0, sizeof(a));
45     memset(mark, 0, sizeof(mark));
46     
47     ans=0;
48     while(scanf("%d", &n)==1)
49     {
50         if(n>=2)
51         {
52             dfs(0);
53         }
54         printf("%d
", ans);
55     }
56     return 0;
57 }

网上别人的代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3   
 4 int main()
 5 {
 6     int k;
 7     scanf("%d", &k);
 8     printf("%d", (int)(pow(2, k) - k - 1) * 2);
 9     return 0;
10 }

算法训练 摆动序列

算法训练摆动序列