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);
        }
    }
}