MENU

HDOJ1257最少拦截系统

July 16, 2018 • Read: 2482 • 算法阅读设置

题目链接: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);
        }
    }
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code