题解 | #拦截导弹# java && c++

Dilworth定理: 最少的下降序列个数就等于整个序列最长上升子序列的长度

//本题用动态规划求解，合唱队那题很有参考价值，可以参考我上一篇题解
// 本题思路  求出 最长递减子序列 即为 一次最多拦截导弹数 逆向思维 求反方向的最长递增子序列
// if (inits[i] >= inits[j]) {dp1[i] = max(dp1[i], dp1[j] + 1 );
// 注意有等号 ， 因为可以相等
// 由Dilworth定理 可知 ，最少下降序列个数即为整个序列最长上升子序列的长度，所以系统套数即为最长上生子序列长度
//  if (inits[i] > inits[j]) {dp2[i] = max(dp2[i], dp2[j] + 1 );}

#include <bits/stdc++.h>
using namespace std;

int main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int length = 0;
    cin >> length;

    int inits[length];
    for (int i = 0; i < length; ++i) {
        cin >> inits[i];
    }

    int dp1[length];
    int dp2[length];

    for (int i = 0; i < length; ++i) {
        dp1[i] = 1;
        dp2[i] = 1;
    }

    int maxLength = 1;
    for (int i = length - 2; i >= 0 ; i--) {
        for (int j = length - 1; j > i ; j--) {
            if (inits[i] >= inits[j]) {
                dp1[i] = max(dp1[i], dp1[j] + 1 );
            }
        }
        maxLength = max(maxLength, dp1[i]);
    }

    int minNumber = 1;
    for (int i = 1; i  < length ; i++) {
        for (int j = 0; j < i ; j++) {
            if (inits[i] > inits[j]) {
                dp2[i] = max(dp2[i], dp2[j] + 1 );
            }
        }
        minNumber = max(minNumber, dp2[i]);
    }

    cout << maxLength << endl;
    cout << minNumber << endl;
}

   import java.io.*;
   import java.util.Arrays;

   public class Main {
	 public static void main(String[] args) throws IOException {
	   StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	   PrintWriter printWriter  = new PrintWriter(new OutputStreamWriter(System.out));
	   streamTokenizer.nextToken();
	   int nums = (int) streamTokenizer.nval;
	   int[] ints = new int[nums];

	   for (int i = 0; i < nums; i++) {
			streamTokenizer.nextToken();
			ints[i] = (int) streamTokenizer.nval;
		}

		int Max = 1;
		int number = 0;
		int[] dp = new int[nums];
		Arrays.fill(dp,1);

		for (int i = nums-2; i >= 0; i--) {
			for (int j = nums - 1; j > i ; j--) {
				if (ints[i] >= ints[j]){
					dp[i] = Math.max(dp[i],dp[j]+1 );
				}
			}
			Max = Math.max(Max,dp[i]);
		}



		int taoshu = 1;
		int[] dp1 = new int[nums];
		Arrays.fill(dp1,1);

		for (int i = 1; i < nums; i++) {
			for (int j = 0; j < i; j++) {
				if (ints[i] > ints[j]){
					dp1[i] = Math.max(dp1[i], dp1[j] + 1 );
				}
			}
			taoshu = Math.max(taoshu,dp1[i]);
		}

		printWriter.println(Max);
		printWriter.println(taoshu);
		printWriter.flush();
}

}