Advertisement
florence20

Untitled

Apr 16th, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.26 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.File;
  3. import java.io.FileReader;
  4. import java.io.IOException;
  5. import java.io.PrintWriter;
  6. import java.util.LinkedList;
  7. import java.util.StringTokenizer;
  8.  
  9. /**
  10. *
  11. * @author florence
  12. */
  13.  
  14. class FinalResult {
  15. long L;
  16. int N;
  17.  
  18. public FinalResult(long L, int N) {
  19. this.L = L;
  20. this.N = N;
  21. }
  22.  
  23. }
  24.  
  25. public class Planificare {
  26. public static final String INPUT_FILE = "planificare.in";
  27. public static final String OUTPUT_FILE = "planificare.out";
  28.  
  29. int p, d, b;
  30. int[] v;
  31. long[][] dp;
  32. int[][] count;
  33. int[] suma;
  34.  
  35. /*
  36. * la citire se populeaza matricea pentru costul lipsurilor +
  37. * matricea pentru nr de concursuri; prima are pe diagonala
  38. * cubul pierderilor daca se considera singure intr-un concurs,
  39. * a doua are pe diagonala 1 pentru ca se pleaca de un singur
  40. * concurs; restul matricei de lipsuri are infinit pentru
  41. * a avea sens comparatiile viitoare
  42. */
  43. public void readInput() {
  44. try {
  45. BufferedReader reader = new BufferedReader(new FileReader(INPUT_FILE));
  46. String first = reader.readLine();
  47. StringTokenizer f = new StringTokenizer(first, " ");
  48. p = Integer.parseInt(f.nextToken());
  49. d = Integer.parseInt(f.nextToken());
  50. b = Integer.parseInt(f.nextToken());
  51. v = new int[p + 1];
  52. dp = new long[p + 1][p + 1];
  53. count = new int[p + 1][p + 1];
  54. suma = new int[p + 1];
  55. String line = reader.readLine();
  56. for (int i = 1; i <= p; i++) {
  57. v[i] = Integer.parseInt(line);
  58. dp[i][i] = (long) Math.pow(d - v[i], 3);
  59. for (int j = i + 1; j <= p; j++) {
  60. dp[i][j] = Long.MAX_VALUE;
  61. }
  62. count[i][i] = 1;
  63. line = reader.readLine();
  64. }
  65. dp[p][p] = 0;
  66. suma[0] = v[0];
  67. for (int i = 1; i < v.length; i++) {
  68. suma[i] = suma[i - 1] + v[i];
  69. }
  70. reader.close();
  71. } catch (IOException e) {
  72. throw new RuntimeException(e);
  73. }
  74. }
  75.  
  76. public void writeOutput(FinalResult result) {
  77. try {
  78. PrintWriter pw = new PrintWriter(new File(OUTPUT_FILE));
  79. pw.printf("%d %d\n", result.L, result.N);
  80. pw.close();
  81. } catch (IOException e) {
  82. throw new RuntimeException(e);
  83. }
  84. }
  85.  
  86. /*
  87. * pentru fiecare subproblema se calculeaza suma lipsurilor
  88. * si se verifica daca poate reprezenta un concurs;
  89. * ultimul element din subsiruri are constul 0 intotdeauna;
  90. * in cazul in care nu se poate forma, cautam subprobleme
  91. * cu k osciland
  92. */
  93. public FinalResult getSolution() {
  94. for (int len = 2; len <= p; ++len) {
  95. for (int i = 1; i + len - 1 <= p; ++i) {
  96. int j = i + len - 1;
  97. long total = suma[j] - suma[i - 1] + (j - i) * b;
  98. if (total <= d) {
  99. count[i][j] = 1;
  100. if (j == p) {
  101. dp[i][j] = 0;
  102. } else {
  103. dp[i][j] = (long) Math.pow(d - total, 3);
  104. }
  105. } else {
  106. for (int k = i; k < j; k++) {
  107. if (dp[i][j] > dp[i][k] + dp[k + 1][j]) {
  108. dp[i][j] = dp[i][k] + dp[k + 1][j];
  109. count[i][j] = count[i][k] + count[k + 1][j];
  110. }
  111. }
  112. }
  113. }
  114. }
  115.  
  116. System.out.println(dp[1][p] + " " + count[1][p]);
  117. return new FinalResult(dp[1][p], count[1][p]);
  118. }
  119.  
  120. public void solve() {
  121. readInput();
  122. writeOutput(getSolution());
  123. }
  124.  
  125. public static void main(String[] args) {
  126. new Planificare().solve();
  127. }
  128.  
  129. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement