题解 | #拦截导弹# java && c++
拦截导弹
https://www.nowcoder.com/practice/218f3db1f66d465bbf9578625aa90785
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(); }
}
动态规划题解 文章被收录于专栏
个人动态规划题解合集