算法题:UVA 10534 Wavio Sequence(dp + LIS)

Wavio is a sequence of integers. It has some interesting properties.

·  Wavio is of odd length i.e. L = 2*n + 1.

·  The first (n+1) integers of Wavio sequence makes a strictly increasing sequence.

·  The last (n+1) integers of Wavio sequence makes a strictly decreasing sequence.

·  No two adjacent integers are same in a Wavio sequence.

For example 1, 2, 3, 4, 5, 4, 3, 2, 0 is an Wavio sequence of length 9. But 1, 2, 3, 4, 5, 4, 3, 2, 2 is not a valid wavio sequence. In this problem, you will be given a sequence of integers. You have to find out the length of the longest Wavio sequence which is a subsequence of the given sequence. Consider, the given sequence as :

1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1.

Here the longest Wavio sequence is : 1 2 3 4 5 4 3 2 1. So, the output will be 9.

Input

The input file contains less than 75 test cases. The description of each test case is given below: Input is terminated by end of file.

Each set starts with a postive integer, N(1<=N<=10000). In next few lines there will be N integers.

Output

For each set of input print the length of longest wavio sequence in a line.
Sample Input                                   Output for Sample Input

Problemsetter: Md. Kamruzzaman, Member of Elite Problemsetters' Panel

时间: 2024-10-29 15:45:46

算法题:UVA 10534 Wavio Sequence(dp + LIS)的相关文章

算法题:UVA 10599 Robots(II)(dp lis)

Your company provides robots that can be used to pick up litter from fields after sporting events and concerts. Before robots are assigned to a job, an aerial photograph of the field is marked with a grid. Each location in the grid that contains garb

算法题之UVA 763

Fibinary Numbers The standard interpretation of the binary number 1010 is 8 + 2 = 10. An alternate way to view the sequence ``1010'' is to use Fibonacci numbers as bases instead of powers of two. For this problem, the terms of the Fibonacci sequence

算法题:uva 10318

题目链接: 首先,可以确定每个格子只能选一次,因为选任何大于0的偶数次,等于没有效果 一样. 然后,就可以把这题理解成从r*c的矩阵中选择一些格子进行"点亮"操作,使得最终所 有格子都是"亮"的状态.那么,每个格子要么有点亮操作,要么没有,总共复杂度为2^25,显然必须 进行减枝. 假设从第一行第一列开始,从左往右,从上往下一次依次选择,对于当前所在位置( x, y),它已经不能影响到x-2以前的行数了,所以当到x行时,如果第x-2行没有全部点亮,则进行减枝 . 此

算法题:uva 1330

题目链接: http://uva.onlinejudge.org/index.php? option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4076 以前做过一道一维的,这题只是变成了二维的,其他方法都一样.HDU 1506  Largest Rectangle in a Histogram   题解 代码1: #include<cstdio> #include<cs

算法:uva 11456

题意 艾琳是个开火车的机师,她也负责车厢的调度.她喜欢把车厢依重量由大到小排列,把最重 的车厢摆在火车的前方. 不幸的是,排列车厢并不容易.你不能直接把一截车厢拿起来放在别处.把一截 车箱插入现有的列车中间并不切实际.一截车厢仅能接在列车的前面或后面. 车厢以事先排定的顺序抵达 车站.当一截车厢抵达时,艾琳可以把它接在列车的前方或后方,或根本不要这截车厢.列车越长越好,但 是其中的车厢要依重量排列. 依车厢抵达的顺序给你车厢的重量,艾琳所能接出的最长火车是多长? 思路 这题算是经典的类型题吧,看

算法题:poj 2541 Binary Witch(KMP水过,逆序转换)

链接: http://poj.org/problem?id=2541 分析与总结: 做这题估算了下复杂度,觉得无论KMP再怎么快,这题暴力也肯定要超时的. 想了很久也没想出个好办法,于是决定暴力之,但是TLE了....于是就放了几天.之后看了下discuss ,这题的正解应该是状态压缩dp,不过目前我还不懂,跪了. 之后百度发现也可以用KMP水过,虽然是因为数据水才过的,不过这种思路很巧妙,值得借鉴! 直接暴力是枚举字符串的后面13个的字母,然后再用KMP匹配,这样的话,就绪要枚举多次,分别是

时间复杂度-求教一个百度面试的算法题

问题描述 求教一个百度面试的算法题 一个有N个元素的一维数组(A[0],A[1], ..., A[n-1]),设计一个算法求解该数组最大子数组.(要求时间复杂度是O(n)) 解决方案 用动态规划http://www.cnblogs.com/xkfz007/archive/2012/05/17/2506299.html 解决方案二: http://www.ahathinking.com/archives/120.html 解决方案三: 哈,这道题啊,已经遇到好多次了,推荐一个很多人都在练习的网站,

从一道算法题说去2

今天的算法题是关于 字符串的最小编辑距离问题求解. 1. 什么是字符串编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数.许可的编辑操作包括将一个字符替换成另一个字符,添加一个字符,删除一个字符. 例如将kitten一字转成sitting: a. sitten (k→s)  b. sittin (e→i)  c. sitting (→g)  俄罗斯科学家Vladimir Levenshtein在1965年提出

一个算法题,求答案啊啊啊啊

问题描述 一个算法题,求答案啊啊啊啊 白班 09:00-18:00 通班 09:00-21:00 每个人每个月通班数量必须等于早中班和中晚班数量之和 早中班 09:00-15:00 中晚班 15:00-21:00 假设:每月按照30计算. 排班规则: 1.每个人每个月固定休息6天连续上班天数不超过7天. 2.每天各班次上班的人数最低需求:8个白班5个通班1个早中班,2个中晚班. 3.每个月每个人的通班天数安排不超过8天. 4.每个人每个月早中班和中晚班的天数之和需要与通班天数相等. 5.每月最多