Advertisement
florence20

Untitled

Apr 16th, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.99 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. public class Planificare {
  25. public final static String INPUT_FILE = "planificare.in";
  26. public final static String OUTPUT_FILE = "planificare.out";
  27.  
  28. int p, d, b;
  29. int[] v;
  30. long dp[][];
  31. int[][] count;
  32. int[] suma;
  33.  
  34. public void readInput(){
  35. try {
  36. BufferedReader reader = new BufferedReader(new FileReader(INPUT_FILE));
  37. String first = reader.readLine();
  38. StringTokenizer f = new StringTokenizer(first, " ");
  39. p = Integer.parseInt(f.nextToken());
  40. d = Integer.parseInt(f.nextToken());
  41. b = Integer.parseInt(f.nextToken());
  42. v = new int[p + 1];
  43. dp = new long[p+1][p+1];
  44. count = new int[p+1][p+1];
  45. suma = new int[p+1];
  46. String line = reader.readLine();
  47. for(int i = 1; i <= p; i++)
  48. {
  49. v[i] = Integer.parseInt(line);
  50. dp[i][i] = (long) Math.pow(d - v[i], 3);
  51. for(int j = i + 1; j <= p; j++){
  52. dp[i][j] = Long.MAX_VALUE;
  53. }
  54. count[i][i] = 1;
  55. line = reader.readLine();
  56. }
  57. dp[p][p] = 0;
  58. suma[0] = v[0];
  59. for(int i = 1; i < v.length; i++)
  60. {
  61. suma[i] = suma[i-1] + v[i];
  62. }
  63. reader.close();
  64. } catch (IOException e){
  65. throw new RuntimeException(e);
  66. }
  67. }
  68.  
  69. public void writeOutput(finalResult result){
  70. try {
  71. PrintWriter pw = new PrintWriter(new File(OUTPUT_FILE));
  72. pw.printf("%d %d\n", result.L, result.N);
  73. pw.close();
  74. } catch( IOException e) {
  75. throw new RuntimeException(e);
  76. }
  77. }
  78.  
  79. public finalResult getSolution(){
  80.  
  81. for (int len = 2; len <= p; ++len) {
  82. for (int i = 1; i + len - 1 <= p; ++i) {
  83. int j = i + len - 1;
  84.  
  85. long total = suma[j] - suma[i-1] + (j-i)*b;
  86. if(total <= d){
  87. count[i][j] = 1;
  88. if(j == p) {
  89. dp[i][j] = 0;
  90. } else {
  91. dp[i][j] = (long) Math.pow(d - total, 3);
  92. }
  93. } else {
  94. for (int k = i; k < j; k++) {
  95. if( dp[i][j] > dp[i][k] + dp[k+1][j] ){
  96. dp[i][j] = dp[i][k] + dp[k+1][j];
  97. count[i][j] = count[i][k] + count[k+1][j];
  98. }
  99. }
  100. }
  101. }
  102. }
  103.  
  104. System.out.println(dp[1][p] + " " + count[1][p]);
  105. return new finalResult(dp[1][p], count[1][p]);
  106. }
  107.  
  108. public void solve(){
  109. readInput();
  110. writeOutput(getSolution());
  111. }
  112.  
  113. public static void main(String[] args) {
  114. new Planificare().solve();
  115. }
  116.  
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement