HDOJ1257最少拦截系统

题目链接：HDOJ1257

思路

这个题一开始我百思不得其解，后来看了一眼别人的题解标题，最长上升子序列？我当时还纳闷，这和最长上升子序列有什么关系，后来仔细一想还确实是。因为导弹拦截系统每次打击的高度只能越来越低，那么我就找越来越高的导弹高度又多少个就行了

举个例子，假设导弹高度分别是2 3 1 4 7，输出应该是4，需要4套拦截系统，五发导弹，为什么只要4个？因为在2 3 4 7这个最长上升子序列中间混入了一个1，1肯定是要比前面的3要小，所以能打击到3的，一定能打击到1，因此1就不用管了，但是越来越高的高度是没法拦截的，所以需要针对2 3 4 7四个导弹分别设一个拦截系统

代码

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int arr[] = new int[10000];
            int dp[] = new int[10000];
            int t = cin.nextInt();
            int ans = 1;
            for(int i = 0;i < t;i++) {
                arr[i] = cin.nextInt();
                dp[i] = 1;
                for(int j = 0;j < i;j++) {
                    if(arr[i] > arr[j])//i作为结尾比j大，构成最长上升子序列
                        dp[i] = Math.max(dp[i],dp[j] + 1);
                }
                ans = Math.max(dp[i],ans);
            }
            System.out.println(ans);
        }
    }
}