【蓝桥杯】算法训练摆动序列(DFS) (9.27)

男娘i 2022-12-11 01:24 139阅读 0赞

不知道dp怎么解决，用的dfs  
这里cnt++的位置：  
我认为：从第二个位置开始，每个位置，有一种数就多了一种状态，  
所以在循环内部写了 if(x >= 2) cnt++;

//2020/10/16--15:30
    //重写了一遍dfs
    #include <iostream>
    #include <cstdlib>
    
    using namespace std;
    const int MAXN = 1e3;
    int vis[MAXN];
    int k, cnt = 0;;
    void dfs(int n1, int n2)
    {
        
        cnt++;
        for (int i = 1; i <= k; i++)
        {
        
            if (vis[i] == 0)
            {
        
                if ((n1 > n2 && i < n2) || (n1 < n2 && i > n2))
                {
        
                    vis[i] = 1;
                    dfs(n2, i);
                    vis[i] = 0;
                }
            }
        }   
    }
    int main()
    {
        
        ios::sync_with_stdio(false);
        cin >> k;
    
        for (int i = 1; i <= k; i++)
        {
        
            vis[i] = 1;
            for (int j = 1; j <= k; j++)
            {
        
                if (vis[j] == 0)
                {
        
                    vis[j] = 1;
                    dfs(i, j);
                }
                vis[j] = 0;
            }
        }
        cout << cnt << endl;
        system("pause");
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关【蓝桥杯训练】DFS与BFS讲解

1. DFS（深度优先遍历）理论介绍 DFS属于图算法的一种，是针对图和树的遍历算法。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序

小咪咪/ 2024年03月25日 14:04/ 0 赞/ 74 阅读

相关蓝桥杯算法训练未名湖边的烦恼（dfs）

算法训练未名湖边的烦恼时间限制：1.0s 内存限制：256.0MB 问题描述　　每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天

梦里梦外;/ 2024年02月17日 20:38/ 0 赞/ 76 阅读

相关蓝桥杯算法训练 - 整数平均值

问题描述编写函数，求包含n个元素的整数数组中元素的平均值。要求在函数内部使用指针操纵数组元素，其中n个整数从键盘输入，输出为其平均值。　　例子样例输入: （输

太过爱你忘了你带给我的痛/ 2022年12月14日 12:29/ 0 赞/ 224 阅读

相关【蓝桥杯】算法训练摆动序列(DFS) (9.27)

不知道dp怎么解决，用的dfs 这里cnt++的位置：我认为：从第二个位置开始，每个位置，有一种数就多了一种状态，所以在循环内部写了 if(x >= 2) cn

男娘i/ 2022年12月11日 01:24/ 0 赞/ 140 阅读

相关【蓝桥杯】蓝桥杯入门训练+蓝桥杯基础训练

BEGIN-1 A+B问题资源限制时间限制：1.0s 内存限制：256.0MB 问题描述输入A、B，输出A+B。输入格式输入的第一行包括两个

野性酷女/ 2022年12月03日 01:59/ 0 赞/ 458 阅读

相关蓝桥杯算法训练矩阵乘法

![这里写图片描述][SouthEast] import java.util.Scanner; public class Main {

ゝ一纸荒年。/ 2022年06月01日 01:20/ 0 赞/ 244 阅读

相关蓝桥杯算法训练数列

问题描述　　给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：　　

本是古典何须时尚/ 2022年04月23日 12:50/ 0 赞/ 331 阅读

相关蓝桥杯算法训练集合运算

问题描述　　给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。输入格式　　第一行为一个整数n，表示集合A中的元素个数。

悠悠/ 2022年03月18日 15:17/ 0 赞/ 287 阅读

相关蓝桥杯算法训练 P0501

输入两个无符号整数x, y, 用位操作实现无符号整数的乘法运算。不用考虑整数的溢出。输入：　　235 657 输出：　　15439

￡神魔★判官ぃ/ 2022年03月18日 12:42/ 0 赞/ 301 阅读

相关蓝桥杯算法训练比赛安排

问题描述　　设有有2 n（n<=6）个球队进行单循环比赛，计划在2 n – 1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2 n – 1天内每个

叁歲伎倆/ 2022年03月18日 12:38/ 0 赞/ 285 阅读