AOJ0572 Card Game is Fun

問題リンク Card Game is Fun

• 解法

Bの連続部分列のうち、Aに部分列として登場するものの中で最大の長さは何かという問題と同義です。Bの中で連続部分列の先頭hを決めたら、Aの中でその数字が一番最初に登場する場所を記録します。以降、一番最初に登場する数字を貪欲に拾っていけば、hから始まってAにも登場する連続部分列の最大の長さが求められます。先頭のhを全て試せば解けます。

• ソース

import java.util.Scanner;

//Card Game is Fun
public class AOJ0572 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt(), B = sc.nextInt();
		int[] a = new int[A], b = new int[B];
		for(int i=0;i<A;i++)a[i]=sc.nextInt();
		for(int i=0;i<B;i++)b[i]=sc.nextInt();
		int res = 0;
		for(int i=0;i<B;i++){
			int v = i, p = 0, k = 0;
			while(v<B&&p<A){
				if(b[v]==a[p]){
					res = Math.max(res, ++k);
					v++;
				}
				p++;
			}
		}
		System.out.println(res);
	}
	
	public static void main(String[] args) {
		new AOJ0572().run();
	}
}