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 final static String INPUT_FILE = "src/planificare.in";
- public final static String OUTPUT_FILE = "src/planificare.out";
- int p, d, b;
- int[] v;
- long dp[][];
- int[][] count;
- int[] suma;
- 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);
- }
- }
- 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