摆动序列算法C语言,ALGO-9_蓝桥杯_算法训练_摆动序列(DP)

问题描述

如果一个序列满足下面的性质，我们就将它称为摆动序列：

. 序列中的所有数都是不大于k的正整数；

. 序列中至少有两个数。

. 序列中的数两两不相等；

. 如果第i – 1个数比第i – 2个数大，则第i个数比第i – 2个数小；如果第i – 1个数比第i – 2个数小，则第i个数比第i – 2个数大。

比如，当k = 3时，有下面几个这样的序列：

一共有8种，给定k，请求出满足上面要求的序列的个数。

输入格式

输入包含了一个整数k。(k<=)

输出格式

输出一个整数，表示满足要求的序列个数。

样例输入

样例输出

记:

注意题目给的条件(当数字大于2时的条件判断,不满足时立即跳出)

AC代码:

#include

#define N 20

int k;

int count = ;

int use[N+] = {}; /*数据存储*/

int vis[N+] = {}; /*访问标记*/

void dfs(int x)

{

int i,j;

int flag;

if (x >= )

{

count ++;

}

if (x > k)

{

return ;

}

for (i = ; i <= k ; i ++)

{

if (!vis[i])

{

flag = ;

use[x] = i;

for (j = x ; j >= ; j --)

{

if (use[j-]>use[j-] && use[j]>use[j-])

{

flag = ;

break;

}

else if (use[j-]

{

flag = ;

break;

}

}

if (flag)

continue;

vis[i] = ;

dfs(x+);

vis[i] = ;

}

}

return ;

}

int main(void)

{

scanf("%d",&k);

dfs();

printf("%d",count);

return ;

}

[蓝桥杯]ALGO-20.算法训练_求先序排列

问题描述 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度<=). 输入格式 两行,每行一个字符串,分别表示中序和后序排列 输出格式 一个字符串,表示所求 ...

[蓝桥杯]ALGO-16.算法训练_进制转换

问题描述 我们可以用这样的方式来表示一个十进制数: 将每个阿拉伯数字乘以一个以该数字所处位置的(值减1)为指数,以10为底数的幂之和的形式.例如:123可表示为 1*102+2*101+3*100这样 ...

[蓝桥杯]ALGO-15.算法训练_旅行家的预算

问题描述 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的).给定两个城市之间的距离D1.汽车油箱的容量C(以升为单位).每升汽油能行驶的距离D2.出发点每升汽油价格P和沿 ...

[蓝桥杯]ALGO-124.算法训练_数字三角形

问题描述 (图3.1-1)示出了一个数字三角形. 请编一个程序计算从顶至底的某处的一条路 径,使该路径所经过的数字的总和最大. ●每一步可沿左斜线向下或右斜线向下走: ●

[蓝桥杯]ALGO-122.算法训练_未名湖边的烦恼

问题描述 每年冬天,北大未名湖上都是滑冰的好地方.北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩. 每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个.现在 ...

[蓝桥杯]ALGO-116.算法训练_最大的算式

问题描述 题目很简单,给出N个数字,不改变它们的相对位置,在中间加入K个乘号和N-K-1个加号,(括号随便加)使最终结果尽量大.因为乘号和加号一共就是N-1个了,所以恰好每两个相邻数字之间都有一个符号 ...

[蓝桥杯]ALGO-101.算法训练_图形显示

问题描述 编写一个程序,首先输入一个整数,例如5,然后在屏幕上显示如下的图形(5表示行数): * * * * * * * * * * * * * * * 题目描述 代码如下: #include < ...

[蓝桥杯]ALGO-97.算法训练_排序

题目描述: 问题描述 编写一个程序,输入3个整数,然后程序将对这三个整数按照从大到小进行排列. 输入格式:输入只有一行,即三个整数,中间用空格隔开. 输出格式:输出只有一行,即排序后的结果. 输入输出 ...

[蓝桥杯]ALGO-92.算法训练_前缀表达式

问题描述 编写一个程序,以字符串方式输入一个前缀表达式,然后计算它的值.输入格式为:“运算符 对象1 对象2”,其中,运算符为“+”(加法).“-”(减法).“*”(乘法)或“/”(除法),运算对象为 ...

[蓝桥杯]ALGO-90.算法训练_出现次数最多的整数

问题描述 编写一个程序,读入一组整数,这组整数是按照从小到大的顺序排列的,它们的个数N也是由用户输入的,最多不会超过20.然后程序将对这个数组进行统计,把出现次数最多的那个数组元素值打印出来.如果有两 ...

随机推荐

C# 定时器 Timers.Timer Forms.Timer

1.定义在System.Windows.Forms里 Windows.Forms里面的定时器比较简单,只要把工具箱中的Timer控件拖到窗体上,然后设置一下事件和间隔时间等属性就可以了 //启动定时器 ...

Windows Azure HandBook (8) Azure性能测试(1)

我们在项目上线之前,常常需要对部署在微软云上的应用软件做压力测试. 一般的压力测试,常常在本地计算机安装压力测试软件 (比如 ...

WebApp MVC，“不一样”的轻量级互联网应用程序开发框架

WebApp MVC 这是一个专门开发互联网程序的开发框架,跟之前的使用情况不一样,EFW主要用于开发行业软件的快速开发:而WebApp又区别与别的MVC框架,比如AspNe ...

HDU 4681 String(DP)

题目链接 枚举A和B中每一段含有C的段,A的前面 后面和B前面后面,求最长公共子序.观察发现,可以预处理最长公共子序. #include #include

Red and Black---hdu1312(dfs)

2015-04-07http://acm.hdu.edu.cn/showproblem.php?pid=1312 Sample Input 6 9....#......#............... ...

linux设备驱动归纳总结(四)：4.单处理器下的竞态和并发【转】

本文转载自:http://blog.chinaunix.net/uid-25014876-id-67005.html linux设备驱动归纳总结(四):4.单处理器下的竞态和并发 xxxxxxxxxx ...

Java 8 VM GC Tunning Guide Charter 7-8-b

第七章 并发gc Java 8提供两种并发gc,CMS和G1 Concurrent Mark Sweep (CMS) Collector This collector is for applicati ...

FPGA 设计总结(1)

1. set_input_delay和set_output_delay的选项-max和-min的理解 首先 input/output其实是模拟数据在端口外的延时,是一个外部约束条件,目的是为了约束FP ...

(class file version 53.0), Java Runtime versions up to 52.0错误的解决方法

遇到这个错误是在Apache Tomcat上部署应用程序的时候遇到的,具体的错误描述是: java.lang.UnsupportedClassVersionError: HelloWorld has ...

frost_vex_01

int inc = 0; //整数inc等于0 while(inc < 6){ //inc在小于6的范围内递增 if(rand(@ptnum + inc + ch("seed" ...