试题算法训练摆动序列

一时失言乱红尘 2024-04-01 02:22 66阅读 0赞

## 试题 算法训练 摆动序列 ##

资源限制  
内存限制：512.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s  
问题描述  
　　如果一个序列满足下面的性质，我们就将它称为摆动序列：  
　　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

**提交代码**：

#include <cstdio>
    #include <iostream>
    using namespace std;
     
    const int maxx = 22;
    int book[maxx],data[maxx];
    int sum,n;
     
    void bfs(int t)
    {
        
    	if(t>1)
    	{
        
    		if(t == 2)
    		{
        
    			sum++;
    		}
    		else
    		{
        
    			int flag = 1;
    			for(int i = t-1; i >= 2;i--)
    			{
        
    				if((data[i - 1] - data[i - 2])*(data[i]-data[i - 2]) >= 0)
    				{
        
    					flag = 0;
    					break;
    				}
    			}
    			if(flag == 1)
    			{
        
    				sum++;
    			}
    			else
    			{
        
    				return ;
    			}
    		}
    	}
    	
    	for(int i = 1;i <= n;i++)
    	{
        
    		if(book[i] == 0)
    		{
        
    			data[t] = i;
    			book[i] = 1;
    			bfs(t + 1);
    			book[i] = 0;
    		}
    	}
    	return ;
    }
     
    int main()
    {
        
    	cin >> n;
    	sum=0;
    	bfs(0);
    	cout << sum <<endl;
    	return 0;
    }