试题算法训练摆动序列

GeekLiHua

发布于 2025-01-21 14:22:13

1360

文章被收录于专栏：JavaJava

试题算法训练摆动序列

资源限制内存限制：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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-07，如有侵权请联系 cloudcommunity@tencent.com 删除

data