首页 > 试题广场 >

B-凌波微步

[编程题]B-凌波微步
  • 热度指数：1 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

小Z的体型实在是太胖了，每次和小D一起出门都跟不上小D的脚步，这让小Z很气馁，于是小Z跋山涉水，仿名山，遍古迹，终于找到了逍遥派。掌门看小Z求师虔诚，决定传小Z一套《凌波微步》。

这种腿法可以无视距离的行进，但缺点是只能走向高处，否则强行发功极易走火入魔。

一天，练习《林波微步》的小Z来到一处练武场，这里从左到右，共有n个木桩，这些木桩有高有低，在这里小Z勤奋的练习着凌波微步，你知道小Z在这处练武场最多能练习多少次么？


输入描述:
本题有T组数据。
对于每组数据第一行有一个正整数n表示有多少个木桩。
第二行有n个数 a_i，表示木桩与水平地面的相对高度。
1≤T≤10
1≤n≤100000
1≤a_i≤1000000000


输出描述:
输出结果，并换行。
示例1

输入

2
6
1 2 3 4 5 6
5
1 3 5 3 6

输出

6
4
算法知识视频讲解
开通博客
头像 马小鸣
发表于 2020-05-20 22:25:52
这道题其实就是一个纸老虎（其实连纸老鼠都不是），但是它却有一个超大的特点——————————那就是坑！！！初读题时，会认为是个LIS，觉得直接从前面来一个，从后面来一个就行。但是，提交上后会“惊喜”的发现超时了。再细细品味时才发现原来就是个水爆了的题目：本题的重点就在于这些木桩的位置其实是可以随意移 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 想润的菠萝蜜在备战秋招
发表于 2022-07-13 14:54:42
排序以后，计算递增的个数就可以了。代码如下： #include<iostream> #include<algorithm> using namespace std; int main() { int t; cin>>t; while(t) { int 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 济南外国语初中_鲁小萱
发表于 2021-11-26 15:42:56
看见这题第一眼就是LIS 于是打完代码交上去发现超时了 回头重新读一遍题 这种腿法可以无视距离的行进 也就是说不用按照顺序跳 那就是一个列表去重求长度了 用python做不要太方便~ 因为输入当做字符串利用set可以不用排序直接去重 反正非常水就对了 Python代码： for t in ran 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Mrboy
发表于 2020-11-22 21:23:00
样例1解释：61 2 3 4 5 6即1->2->3->4->5->6共6个数字 样例2解释：51 3 5 3 6即1->3->5->6共4个数字解法：排序+去重
去ta的博客 赞 (0) 回复(0) 收起
头像 已注销
发表于 2021-05-21 11:54:51
include<stdio.h> include<stdlib.h> int cmp ( const void *a, const void *b ){ return *(int *)a - *(int *)b; //强制转换类型}int main(){ int 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 既原又崩
发表于 2023-09-19 19:31:32
set容器符合题意 set容器特点 自动排序 删除重复 #include <iostream> using namespace std; #include <set> void solve() { int x; cin >> x; set 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

堆/优先队列 STL
难度：
0条回答 68浏览

热门推荐

通过挑战的用户

查看代码

相关试题

B-凌波微步

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号