一， 最长递增子序列问题的描述
设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。求最大的m值。
二，算法：动态规划法:O(n^2)
设f(i)表示L中以ai为末元素的最长递增子序列的长度。则有如下的递推方程：
这个递推方程的意思是，在求以ai为末元素的最长递增子序列时，找到所有序号在L前面且小于ai的元素aj，即j<i且aj<ai。如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度f(j)，把其中最大的f(j)选出来，那么f(i)就等于最大的f(j)加上1，即以ai为末元素的最长递增子序列，等于以使f(j)最大的那个aj为末元素的递增子序列最末再加上ai；如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。一般在解决问题的时候都是用到动态规划.
NYOJ 17 http://acm.nyist.net/JudgeOnline/problem.php?pid=17
单调递增最长子序列
时间限制：3000 ms | 内存限制：65535 KB
难度：4
- 描述
- 求一个字符串的最长递增子序列的长度
如：dabdbf最长递增子序列就是abdf，长度为4
- 输入
- 第一行一个整数0<n<20,表示有n个字符串要处理
随后的n行，每行有一个字符串，该字符串的长度不会超过10000 - 输出
- 输出字符串的最长递增子序列的长度
- 样例输入
-
3
aaa
ababc
abklmncdefg - 样例输出
-
1
3
7#include<stdio.h>
#include<string.h>
int main()
{
int a[],i,j,n;
char s[];
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
int max,len=strlen(s);
for(i=;i<len;i++)
a[i]=;
for(i=;i<len;i++)
{
max=;
for(j=;j<i;j++)
{
if(s[j]<s[i]&&max<a[j])
{
max=a[j];
}
}
a[i]=max+;
}
max=a[];
for(i=;i<len;i++)
{
if(a[i]>max)
max=a[i];
}
printf("%d\n",max);
}
return ;
}NYOJ 79http://acm.nyist.net/JudgeOnline/problem.php?pid=79
描述
某国为了防御敌国的导弹袭击，发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于等于前一发的高度。某天，雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段，所以只用一套系统，因此有可能不能拦截所有的导弹。
- 输入
- 第一行输入测试数据组数N（1<=N<=10）
接下来一行输入这组测试数据共有多少个导弹m（1<=m<=20）
接下来行输入导弹依次飞来的高度，所有高度值均是大于0的正整数。 - 输出
- 输出最多能拦截的导弹数目
- 样例输入
-
2
8
389 207 155 300 299 170 158 65
3
88 34 65 - 样例输出
-
6
2#include<stdio.h>
#include<string.h>
int main()
{
int f[],i,j,n,a[],max;
scanf("%d",&n);
while(n--)
{
int t;
scanf("%d",&t);
for(i=;i<t;i++)
scanf("%d",&a[i]);
f[]=;
for(i=;i<t;i++)
{
max=;
for(j=;j<i;j++)
{
if(a[j]>a[i]&&max<f[j])
{
max=f[j];
}
}
f[i]=max+;
}
max=f[];
for(i=;i<t;i++)
{
if(f[i]>max)
max=f[i];
}
printf("%d\n",max);
}
return ;
}