|
|
back to boardwhy wrong 7 I use dp code. /////////////////// import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.StreamTokenizer; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; public class Timus_1651 { static StreamTokenizer st; public static void main(String[] args) throws IOException{ st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); int n = nextInt(); int []a = new int [n+1]; for (int i = 1; i <=n; i++) { a[i] = nextInt(); } int []dp = new int [100001]; int []p = new int [100001]; int INF = (int)1e8; Arrays.fill(dp, INF); dp[a[1]] = 0; for (int i = 2; i <=n; i++) { if (dp[a[i]] > dp[a[i-1]]+1){ dp[a[i]] = dp[a[i-1]]+1; p[a[i]] = a[i-1]; } } int cur = a[n]; ArrayList<Integer> ans = new ArrayList<Integer>(); while (true){ ans.add(cur); if (cur == a[1]) break; cur = p[cur]; } Collections.reverse(ans); for (int i = 0; i < ans.size(); i++) { out.write(ans.get(i)+" "); } out.close(); } private static int nextInt() throws IOException{ st.nextToken(); return (int) st.nval; } } |
|
|