一、信息学OJ：1281：最长上升子序列

(1)问题描述

        

一个数的序列bibi，当b1<b2<...<bSb1<b2<...<bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,...,aN)(a1,a2,...,aN)，我们可以得到一些上升的子序列(ai1,ai2,...,aiK)(ai1,ai2,...,aiK)，这里1≤i1<i2<...<iK≤N1≤i1<i2<...<iK≤N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,5,8)。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

【输入】

输入的第一行是序列的长度N(1≤N≤1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

【输出】

最长上升子序列的长度。

【输入样例】

7
1 7 3 5 9 4 8

【输出样例】

4

(2)代码实现

         

#include <stdio.h>
#define MAXN 1010
int a[MAXN],f[MAXN]; 
int max(int x,int y)
{
	return x > y ? x : y;
}
int main()
{
	int n;
	int i,j,ans=1;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[i]=1;     // 初始化f[i]
	}
	// 动态更新f[i]
	for(i=2;i<=n;i++)
	{
		for(j=1;j<i;j++)
		{
        	if(a[i]>a[j])
				f[i]=max(f[i],f[j]+1);
		}
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}

二、信息学OJ： 1260：【例9.4】拦截导弹(Noip1999)

(1)问题描述

        

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

【输入】

输入导弹依次飞来的高度。

【输出】

第一行：最多能拦截的导弹数；

第二行：要拦截所有导弹最少要配备的系统数。

【输入样例】

389 207 155 300 299 170 158 65

【输出样例】

6
2

(2)代码实现

        

#include <stdio.h>
#define N 1010
 
int dp1[N];           
int dp2[N];            
int f[N];            
 
int max(int x,int y)
{
	return x > y ? x : y;
}
 
int main()
{
	int idx=0,ans=0,cnt=0;
	int i,j;
	while(scanf("%d", &f[idx])!=EOF)          
		idx++;
	for(i=0;i<idx;i++)
	{
		dp1[i]=dp2[i]=1;
		for(j=0;j<i;j++)
		{
			if(f[i]<=f[j])                   
				dp1[i]=max(dp1[i],dp1[j]+1);
			else                              
				dp2[i]=max(dp2[i],dp2[j]+1);
		}
		if(ans<dp1[i])
			ans=dp1[i];
		if(cnt<dp2[i])
			cnt=dp2[i];
	}
	printf("%d\n%d\n",ans,cnt);
	return 0;
}

三、蓝桥杯 试题 算法提高 最长公共子序列

(1)问题描述

        

问题描述

　　给定两个字符串，寻找这两个字串之间的最长公共子序列。

输入格式

　　输入两行，分别包含一个字符串，仅含有小写字母。

输出格式

　　最长公共子序列的长度。

样例输入

abcdgh
aedfhb

样例输出

3

样例说明

　　最长公共子序列为a，d，h。

数据规模和约定

　　字串长度1~1000。

(2)代码实现

        

import java.util.*;

public class Main {
    static Scanner in=new Scanner(System.in);
    static int a,b;
    public static void main(String[] args) {
        String a=in.next();
        String b=in.next();
        int n=a.length(),m=b.length();
        int[][] f=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            char c1=a.charAt((i-1));
            for(int j=1;j<=m;j++){
                char c2=b.charAt(j-1);
                if(c1==c2) f[i][j]=f[i-1][j-1]+1;
                else f[i][j]=Math.max(f[i-1][j],f[i][j-1]);
            }
        }
        System.out.println(f[n][m]);
    }
}