1小朋友排队2摆动序列

超、凢脫俗 2022-10-29 09:11 68阅读 0赞

error: reference to ‘left’ is ambiguous|  
是和库的变量名重复了，解决方法：修改变量名

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

http://lx.lanqiao.cn/problem.page?gpid=T44  
问题描述  
　　如果一个序列满足下面的性质，我们就将它称为摆动序列：  
　　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，请求出满足上面要求的序列的个数。

#include <iostream>
    using namespace std;
    int k,ans;
    int a[100];
    bool vis[100];  //标记是否访问
    //判断当前点是否满足要求
    bool judge(int num, int x) {
        
    	if (x == 1 || x == 2)
    		return true;
    	if ((a[x - 1] - a[x - 2]) * (num - a[x - 2]) < 0)
    		return true;
    	return false;
    }
    void dfs(int x) {
        
    	//大于要求长度则返回
    	if (x > k)
    		return;
    	for (int i = 1; i <= k; ++i) {
        
    		if (!vis[i] && judge(i, x)) {
        
    			vis[i] = true;
    			a[x] = i;
    			//序列必须大于2，才计数
    			if (x >= 2)
    				ans++;
    			dfs(x + 1);
    			vis[i] = false;  //回溯
    		}
    	}
    }
    int main() {
        
    	cin >>k;
    	dfs(1);
    	cout << ans << endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，68人围观）

还没有评论，来说两句吧...

相关阅读

相关试题算法训练摆动序列

试题算法训练摆动序列资源限制内存限制：512.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s 问题描述

一时失言乱红尘/ 2024年04月01日 02:22/ 0 赞/ 70 阅读

相关 376. 摆动序列

376. 摆动序列题干描述解题思路思路1（贪心解法）情况一：上下坡中有平坡情况二：数组首尾两端

ゝ一世哀愁。/ 2023年10月16日 14:58/ 0 赞/ 5 阅读

相关贪心——376. 摆动序列

1 题目描述如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也

深碍√TFBOYSˉ_/ 2023年10月08日 16:16/ 0 赞/ 27 阅读

相关算法-贪心-摆动序列（摇摆序列）

算法-贪心-摆动子序列（摇摆子序列/Wiggle Subsequence） 1 题目概述 1.1 题目出处 https://leetcode-cn.com/p

傷城~/ 2023年07月25日 09:54/ 0 赞/ 10 阅读

相关 leetcode376. 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。例如， \[1,7,4,9

「爱情、让人受尽委屈。」/ 2023年07月05日 10:03/ 0 赞/ 9 阅读

相关 LeetCode 376. 摆动序列

解题思路时间复杂度并不理想，没有想到使用波峰，波谷的o(n)算法。这个dp也还勉强可以通过。思路就是先计算出差值，然后对差值数组进行dp即可。代码

比眉伴天荒/ 2023年07月03日 08:17/ 0 赞/ 7 阅读

相关【贪心】 LeetCode376. 摆动序列

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

古城微笑少年丶/ 2022年12月03日 13:21/ 0 赞/ 148 阅读

相关 1小朋友排队2摆动序列

error: reference to ‘left’ is ambiguous| 是和库的变量名重复了，解决方法：修改变量名试题算法训练摆动序列 htt

超、凢脫俗/ 2022年10月29日 09:11/ 0 赞/ 69 阅读

相关 leetcode 376 摆动序列

前言题目：[376. 摆动序列][376.] 参考题解：[摆动序列-代码随想录][-] -------------------- 提交代码这道题目，我没想

深藏阁楼爱情的钟/ 2022年09月14日 09:48/ 0 赞/ 147 阅读

相关蓝桥杯历届试题小朋友排队

历届试题小朋友排队时间限制：1.0s 内存限制：256.0MB 问题描述　　n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两

清疚/ 2022年08月21日 04:58/ 0 赞/ 261 阅读