Advertisement
limimage

H3

Sep 18th, 2019
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.84 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class oaks_md implements Runnable {
  5. private Scanner in;
  6. private PrintWriter out;
  7.  
  8. public void run() {
  9. try {
  10. in = new Scanner(new FileReader("oaks.in"));
  11. out = new PrintWriter(new File("oaks.out"));
  12. solve();
  13. in.close();
  14. out.close();
  15. } catch (IOException e) {
  16. e.printStackTrace();
  17. System.exit(1);
  18. }
  19. }
  20.  
  21. int n;
  22. int[] a;
  23. boolean[][] wipe;
  24. int[][] howWipe;
  25. int[] max;
  26. int[] how;
  27.  
  28. public void solve() {
  29. n = in.nextInt();
  30. a = new int[n];
  31. wipe = new boolean[n][n];
  32. howWipe = new int[n][n];
  33. max = new int[n];
  34. how = new int[n];
  35. for (int i = 0; i < n; i++) {
  36. a[i] = in.nextInt();
  37. }
  38. for (int i = 0; i < n - 1; i++) {
  39. wipe[i][i + 1] = true;
  40. howWipe[i][i + 1] = -1;
  41. }
  42. for (int d = 2; d < n; d++) {
  43. for (int i = 0, j; (j = i + d) < n; i++) {
  44. for (int k = i + 1; k < j; k++) {
  45. if (a[k] > Math.max(a[i], a[j]) || a[k] < Math.min(a[i], a[j])) {
  46. if (wipe[i][k] && wipe[k][j]) {
  47. wipe[i][j] = true;
  48. howWipe[i][j] = k;
  49. break;
  50. }
  51. }
  52. }
  53. }
  54. }
  55. max[0] = 1;
  56. for (int i = 1; i < n; i++) {
  57. max[i] = 0;
  58. for (int j = 0; j < i; j++) {
  59. if (max[j] > 0 && wipe[j][i] && a[j] <= a[i] && max[j] + 1 > max[i]) {
  60. max[i] = max[j] + 1;
  61. how[i] = j;
  62. }
  63. }
  64. }
  65. if (max[n - 1] == 0) {
  66. out.println(-1);
  67. return;
  68. }
  69. out.println(n - max[n - 1]);
  70. cut(n - 1);
  71. }
  72.  
  73. private void cut(int v) {
  74. if (v == 0)
  75. return;
  76. cut(how[v]);
  77. wipe(how[v], v);
  78. }
  79.  
  80. private void wipe(int u, int v) {
  81. int w = howWipe[u][v];
  82. if (w < 0)
  83. return;
  84. wipe(u, w);
  85. wipe(w, v);
  86. out.println(w + 1);
  87. }
  88.  
  89. public static void main(String[] args) throws IOException {
  90. Locale.setDefault(Locale.US);
  91. new Thread(new oaks_md()).start();
  92. }
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement