testingthecatcher.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.*;

/**
 * ID:1887
 * 动态规划，result[i]是以i结尾（必须包括i）的前面的数中最长的长度
 * @author yhm
 *
 */
public class TestingtheCATCHER {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int i=1;
		while(true){
			int in=-1;
			List<Integer> l = new ArrayList<Integer>();
			while((in=cin.nextInt())!=-1){
				l.add(in);
			}
			if(l.isEmpty()) break;
			int r = solve(l);
			System.out.println("Test #"+i+":");
			System.out.println("  maximum possible interceptions: "+r);
			System.out.println();
			i++;
		}

	}

	static int solve(List<Integer> l){
		int size = l.size();
		int[] result = new int[size];
		Arrays.fill(result, 1);
		int maxValue = 1;
		for(int i=1;i<size;i++){
			int max = 0;
			for(int j=i-1;j>=0;j--){
				if(l.get(j)>=l.get(i) && result[j]>=max){
					max = result[j]; 
				}
			}
			
			result[i] = max+1;
			maxValue = Math.max(result[i], maxValue);
		}
		return maxValue;
	}
}