[伯俊]14002回成長最長の部分数列4-Java,Java
難易度
金貨.
質問する
https://www.acmicpc.net/problem/14002!
に答える 11053回の成長が最も長い不可逆数列に類似している。 11053番と同じですが、最も長い部分の列を出力する必要があります。 dp配列に格納された値を用いて逆トラッキングコードを記述すればよい。 コード#コード# import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; //140002回成長最長の部分数列4 public class boj_11_14002 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int n = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()); int arr[] = new int[n + 1]; int dp[] = new int[n + 1]; for (int i = 1; i <= n; i++) { arr[i] = Integer.parseInt(st.nextToken()); } dp[1] = 1; int ans = 1; for (int i = 2; i <= n; i++) { dp[i] = 1; for (int j = 1; j < i; j++) { if (arr[i] > arr[j] && dp[i] <= dp[j]) { dp[i] = dp[j] + 1; } } ans = Math.max(ans, dp[i]); } //リバーストレース //最長値 int value = ans; Stack<Integer> stack = new Stack<>(); for (int i = n; i >= 1; i--) { if (value == dp[i]) { stack.push(arr[i]); value--; } } while (!stack.isEmpty()) { sb.append(stack.pop() + " "); } System.out.println(ans); System.out.println(sb); } }
金貨.
質問する
https://www.acmicpc.net/problem/14002!
に答える 11053回の成長が最も長い不可逆数列に類似している。 11053番と同じですが、最も長い部分の列を出力する必要があります。 dp配列に格納された値を用いて逆トラッキングコードを記述すればよい。 コード#コード# import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringTokenizer; //140002回成長最長の部分数列4 public class boj_11_14002 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int n = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()); int arr[] = new int[n + 1]; int dp[] = new int[n + 1]; for (int i = 1; i <= n; i++) { arr[i] = Integer.parseInt(st.nextToken()); } dp[1] = 1; int ans = 1; for (int i = 2; i <= n; i++) { dp[i] = 1; for (int j = 1; j < i; j++) { if (arr[i] > arr[j] && dp[i] <= dp[j]) { dp[i] = dp[j] + 1; } } ans = Math.max(ans, dp[i]); } //リバーストレース //最長値 int value = ans; Stack<Integer> stack = new Stack<>(); for (int i = n; i >= 1; i--) { if (value == dp[i]) { stack.push(arr[i]); value--; } } while (!stack.isEmpty()) { sb.append(stack.pop() + " "); } System.out.println(ans); System.out.println(sb); } }
Reference
この問題について([伯俊]14002回成長最長の部分数列4-Java,Java), 我々は、より多くの情報をここで見つけました https://velog.io/@kimmjieun/백준-14002번-가장-긴-증가하는-부분-수열-4-Java-자바テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol