藍橋杯 擺動序列(df


#include <stdio.h>
#include <string.h>

int a[100];//擺動數組
int vis[100];
int k;
int ans;

bool judge(int x,int Index)
{
if(Index == 1 || Index == 2)
return true;
if(a[Index - 1] > a[Index - 2] && x < a[Index - 2])
return true;
if(a[Index - 1] < a[Index - 2] && x > a[Index - 2])
return true;
return false;
}

void dfs(int count)
{
if(count > k)
return ;
for (int i = 1; i <= k; ++i)
{
if(!vis[i] && judge(i,count))
{
vis[i] = 1;
a[count] = i;
if(count >= 2)
ans++;
dfs(count+1);
vis[i] = 0;
}
}
}

int main()
{
scanf("%d",&k);
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
ans = 0;
dfs(1);
printf("%d\n",ans);
}



問題描述

  如果一個序列滿足下面的性質,我們就將它稱為擺動序列:

  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)

輸出格式

  輸出一個整數,表示滿足要求的序列個數。


樣例輸入

3

樣例輸出

8

0 個評論

要回覆文章請先登錄註冊