杭电1423（Greatest Common Increasing Subsequence）

点击打开杭电1423

Problem Description

This is a problem from ZOJ 2432.To make it easyer,you just need output the length of the subsequence.

Input

Each sequence is described with M – its length (1 <= M <= 500) and M integer numbers Ai (-2^31 <= Ai < 2^31) – the sequence itself.

Output

output print L – the length of the greatest common increasing subsequence of both sequences.

Sample Input

151 4 2 5 -124-12 1 2 4

Sample Output

2

题意：求最长公共递增子序列的长度，直接要用模板即可（最长递增公共子序列）

代码实现：

import java.util.Scanner;class P1423 {static int[] a,b,dp;static int n,m;public static void main(String[] args) {Scanner sc=new Scanner(System.in);int t=sc.nextInt();while(t–>0){n=sc.nextInt();a=new int[n+1];for(int i=1;i<=n;i++){a[i]=sc.nextInt();}m=sc.nextInt();b=new int[m+1];for(int i=1;i<=m;i++){b[i]=sc.nextInt();}System.out.println(LICS());if(t!=0){System.out.println();}}}public static int LICS() {int i,j,Max;int lengMax=Math.max(n, m);dp=new int[lengMax+1];for(i=1;i<=n;i++){Max=0;for(j=1;j<=m;j++){if(a[i]>b[j] && Max<dp[j]){Max=dp[j];}if(a[i]==b[j]){dp[j]=Max+1;}}}Max=0;for(i=1;i<=m;i++){if(Max<dp[i]){Max=dp[i];}}return Max;}}

，靠山山会倒，靠人人会跑，只有自己最可靠。