- 浏览: 32695 次
最新评论
对于序列(1, 7, 3, 5, 9, 4,,有它的一些不下降子序列
如(1, 7), (3, 4,等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5,。
Input
多组cas , 每组cas 两行:
第一行 输入一个数 n (n < 10000), 表示有n个数
第二行 n个数, 分别代表每个数;
Output
每个cas 一行 输出 该书数列的最长的长度 ;
Sample Input
7
1 7 3 5 9 4 8
Sample Output
4
#include<iostream>
using namespace std;
#define MAX 10001
void vInput(int nN,int nA[]);
int nGetLong(int nN,int nA[]);
int nFind(int nUL[],int nA,int nHigh,int Low);
void vOut(int nOut);
int main()
{
int nNum;
int nArr[MAX];
int nAns;
while(1==scanf("%d",&nNum))
{
vInput(nNum,nArr);
nAns=nGetLong(nNum,nArr);
vOut(nAns);
}
return 0;
}
void vInput(int nN,int nA[])
{
int i;
for(i=1;i<=nN;i++)
{
scanf("%d",&nA[i]);
}
}
int nGetLong(int nN,int nA[])
{
int i;
int nCount;
int nUpLimit[MAX];
int nPos;
for(i=1;i<=nN;i++)
{
nUpLimit[i]=nA[nN];
}
nCount=1;
for(i=nN-1;i>=1;i--)
{
if(nA[i]<=nUpLimit[nCount])
{
nCount++;
nUpLimit[nCount]=nA[i];
}
else
{
nPos=nFind(nUpLimit,nA[i],nCount,1);
nUpLimit[nPos]=nA[i];
}
}
return nCount;
}
int nFind(int nUL[],int nA,int nHigh,int nLow)
{
int nMid;
int nRet;
nMid=(nHigh+nLow)/2;
if(nHigh==nLow)
{
nRet=nHigh;
return nRet;
}
if(nA>nUL[nMid])
{
nRet=nFind(nUL,nA,nMid,nLow);
}
else
nRet=nFind(nUL,nA,nHigh,nMid+1);
return nRet;
}
void vOut(int nOut)
{
printf("%d\n",nOut);
}
如(1, 7), (3, 4,等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5,。
Input
多组cas , 每组cas 两行:
第一行 输入一个数 n (n < 10000), 表示有n个数
第二行 n个数, 分别代表每个数;
Output
每个cas 一行 输出 该书数列的最长的长度 ;
Sample Input
7
1 7 3 5 9 4 8
Sample Output
4
#include<iostream>
using namespace std;
#define MAX 10001
void vInput(int nN,int nA[]);
int nGetLong(int nN,int nA[]);
int nFind(int nUL[],int nA,int nHigh,int Low);
void vOut(int nOut);
int main()
{
int nNum;
int nArr[MAX];
int nAns;
while(1==scanf("%d",&nNum))
{
vInput(nNum,nArr);
nAns=nGetLong(nNum,nArr);
vOut(nAns);
}
return 0;
}
void vInput(int nN,int nA[])
{
int i;
for(i=1;i<=nN;i++)
{
scanf("%d",&nA[i]);
}
}
int nGetLong(int nN,int nA[])
{
int i;
int nCount;
int nUpLimit[MAX];
int nPos;
for(i=1;i<=nN;i++)
{
nUpLimit[i]=nA[nN];
}
nCount=1;
for(i=nN-1;i>=1;i--)
{
if(nA[i]<=nUpLimit[nCount])
{
nCount++;
nUpLimit[nCount]=nA[i];
}
else
{
nPos=nFind(nUpLimit,nA[i],nCount,1);
nUpLimit[nPos]=nA[i];
}
}
return nCount;
}
int nFind(int nUL[],int nA,int nHigh,int nLow)
{
int nMid;
int nRet;
nMid=(nHigh+nLow)/2;
if(nHigh==nLow)
{
nRet=nHigh;
return nRet;
}
if(nA>nUL[nMid])
{
nRet=nFind(nUL,nA,nMid,nLow);
}
else
nRet=nFind(nUL,nA,nHigh,nMid+1);
return nRet;
}
void vOut(int nOut)
{
printf("%d\n",nOut);
}
发表评论
-
最大子段和
2012-01-05 13:59 779给出N个数字, 计算出最大的子段和。 Input 第一行给 ... -
求两字符串匹配的最长子序列
2012-01-05 13:52 1016如果两种特征序列的公共子序列越长表示越接近,现在请你帮助计算出 ... -
编辑距离问题
2012-01-05 13:48 658#include<iostream> #incl ... -
Kruskal最小生成树
2011-12-08 14:26 700#include<iostream> #inclu ... -
prime
2011-12-01 20:09 612#include<iostream> using ... -
哈弗曼编码
2011-11-28 10:43 1#include<iostream> #defi ... -
哈弗曼编码
2011-11-28 10:42 521#include<iostream> #defi ... -
#贪心算法(零件加工)
2011-10-27 13:25 981#include<stdio.h> #includ ... -
众数问题
2011-10-20 14:57 790#include <stdio.h> #inclu ... -
输油管道问题
2011-10-13 14:45 599#include <stdio.h> #inclu ... -
幂的精确求值
2011-09-22 15:07 461#include<iostream> using ... -
大数加法
2011-09-22 12:56 607#include<iostream> #incl ... -
三姐妹之出题
2011-09-15 14:15 663#include<iostream> #incl ... -
最大子段和问题(分治)(##)
2011-09-08 21:31 665#include<stdio.h> #defin ... -
最大子段和问题(O(N^2))
2011-09-08 15:04 610#include<stdio.h> int a[ ... -
最大子段和问题(O(N^3))
2011-09-08 14:45 476#include<stdio.h> int a[ ...
相关推荐
最长不下降子序列一些介绍
运用动态规划算法解决最长公共子序列问题,计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=, x2, …, xm>和Y=, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与...
最长不升公共子序列问题的动态规划算法,结果求出了子序列的长度以及该子序列是什么,采用的是Java。
如果已知一个序列中最长的不下降子序列长度,那么这个序列前面添加一个数之后的最长的不下降子序列长度可能加1,这与原来的最长不下降子序列中最大的两个数有关。 具体是,如果加的数比子序列最大值大,长度加1。...
最长不减子序列,动态规划 C++代码, 其实主要是理解其中动态规划的思想,减少复杂度
给定一个无序的整数数组,找到其中最长上升子序列的长度。 上升子序列指的是一个子序列,它的每个元素都严格大于它前面的元素。最长上升子序列则是指所有上升子序列中最长的那一个。 以下是使用动态规划求解最长...
要求:给定一个数字序列,任意次序,找出其中的最长非递增子序列的长度,输出该长度值. 程序用动态规划的方法予以实现.
求最长不下降序列 求最长不下降序列 求最长不下降序列 求最长不下降序列
Description 一个给定序列的子序列是在该序列中删去若干元素后得到的...你的输出应该有C行,即每组测试数据的输出占一行,它是计算出的最长公共子序列长度。 Sample Input 1 ABCBDBA BDCABA Sample Output 4
动态规划:最长单调递增子序列 A numeric sequence of ai is ordered if a1 (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 , sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. ...
设有一个正整数的序列:b1, b2, …bn, 对于下标i1…ih, 若有bi1…,则称存在一个长度为h的不下降序列。 例如,下列数 ...问题:当给定b1, b2, …bn后,求出最长的不下降序列h及这个序列中的各个数。
1925最长下降子序列1925最长下降子序列1925最长下降子序列
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
提供了求出最长上升子序列中各个元素的个数以及打印出各个元素的方法,希望能对大家有所帮助。
问题描述 设有整数序列b1,b2,b3,…,bm,若存在 i1 … ,且 bi1 …,则称b1,b2,b3,…,bm中有长度为n的不下降序列bi1,bi2,bi3,…,bin。求序列中最大不下降子序列长度k。
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。(用递归和动态规划算法分别解决并比较计算时间)例如: 输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为...
60、【例9.3】求最长不下降序列(2020.01.24)-A 60、【例9.3】求最长不下降序列(2020.01.24)-A 60、【例9.3】求最长不下降序列(2020.01.24)-A
用Python实现动态规划中最长公共子序列和最长公共子串问题!
C++求最长公共子序列!实用 花费了好长时间!!
由此函数,把序列X={x1,x2….xm}和Y={y1,y2…ym}的最长公共子序列的搜索分为M个阶段,第1阶段,按照式1计算X1和Yj的最长公共子序列长度L[1][j](1),第2阶段,按照2式计算X2和Yj的最长公共子序列长度L[2][j](1),...