Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.File;
- import java.io.FileReader;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.util.LinkedList;
- import java.util.StringTokenizer;
- /**
- *
- * @author florence
- */
- class FinalResult {
- long L;
- int N;
- public FinalResult(long L, int N) {
- this.L = L;
- this.N = N;
- }
- }
- public class Planificare {
- public static final String INPUT_FILE = "planificare.in";
- public static final String OUTPUT_FILE = "planificare.out";
- int p, d, b;
- int[] v;
- long[][] dp;
- int[][] count;
- int[] suma;
- /*
- * la citire se populeaza matricea pentru costul lipsurilor +
- * matricea pentru nr de concursuri; prima are pe diagonala
- * cubul pierderilor daca se considera singure intr-un concurs,
- * a doua are pe diagonala 1 pentru ca se pleaca de un singur
- * concurs; restul matricei de lipsuri are infinit pentru
- * a avea sens comparatiile viitoare
- */
- public void readInput() {
- try {
- BufferedReader reader = new BufferedReader(new FileReader(INPUT_FILE));
- String first = reader.readLine();
- StringTokenizer f = new StringTokenizer(first, " ");
- p = Integer.parseInt(f.nextToken());
- d = Integer.parseInt(f.nextToken());
- b = Integer.parseInt(f.nextToken());
- v = new int[p + 1];
- dp = new long[p + 1][p + 1];
- count = new int[p + 1][p + 1];
- suma = new int[p + 1];
- String line = reader.readLine();
- for (int i = 1; i <= p; i++) {
- v[i] = Integer.parseInt(line);
- dp[i][i] = (long) Math.pow(d - v[i], 3);
- for (int j = i + 1; j <= p; j++) {
- dp[i][j] = Long.MAX_VALUE;
- }
- count[i][i] = 1;
- line = reader.readLine();
- }
- dp[p][p] = 0;
- suma[0] = v[0];
- for (int i = 1; i < v.length; i++) {
- suma[i] = suma[i - 1] + v[i];
- }
- reader.close();
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- public void writeOutput(FinalResult result) {
- try {
- PrintWriter pw = new PrintWriter(new File(OUTPUT_FILE));
- pw.printf("%d %d\n", result.L, result.N);
- pw.close();
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- /*
- * pentru fiecare subproblema se calculeaza suma lipsurilor
- * si se verifica daca poate reprezenta un concurs;
- * ultimul element din subsiruri are constul 0 intotdeauna;
- * in cazul in care nu se poate forma, cautam subprobleme
- * cu k osciland
- */
- public FinalResult getSolution() {
- for (int len = 2; len <= p; ++len) {
- for (int i = 1; i + len - 1 <= p; ++i) {
- int j = i + len - 1;
- long total = suma[j] - suma[i - 1] + (j - i) * b;
- if (total <= d) {
- count[i][j] = 1;
- if (j == p) {
- dp[i][j] = 0;
- } else {
- dp[i][j] = (long) Math.pow(d - total, 3);
- }
- } else {
- for (int k = i; k < j; k++) {
- if (dp[i][j] > dp[i][k] + dp[k + 1][j]) {
- dp[i][j] = dp[i][k] + dp[k + 1][j];
- count[i][j] = count[i][k] + count[k + 1][j];
- }
- }
- }
- }
- }
- System.out.println(dp[1][p] + " " + count[1][p]);
- return new FinalResult(dp[1][p], count[1][p]);
- }
- public void solve() {
- readInput();
- writeOutput(getSolution());
- }
- public static void main(String[] args) {
- new Planificare().solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement