fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.     private static class Matrix {
  5.         private int width;
  6.         private int height;
  7.  
  8.         public Matrix(int width, int height) {
  9.             this.width = width;
  10.             this.height = height;
  11.         }
  12.     }
  13.  
  14.     private static long multiple(long[][] dp, Matrix[] sizes, int[][] bestCut, int l, int r ) {
  15.         if (dp[l][r] == Long.MAX_VALUE) {
  16.             for (int i = l; i < r; i++) {
  17.             long cur = multiple(dp, sizes, bestCut, l, i) + multiple(dp, sizes, bestCut, i + 1, r) + sizes[l].width * sizes[i].height * sizes[r].height;
  18.                 if (cur < dp[l][r]) {
  19.                     dp[l][r] = cur;
  20.                     bestCut[l][r] = i;
  21.                 }
  22.             }
  23.         }
  24.         return dp[l][r];
  25.     }
  26.  
  27.     private static void print(int l, int r, int[][] bestCut) {
  28.         if (l == r) {
  29.             System.out.print("A" + (l + 1));
  30.         }
  31.         else {
  32.             System.out.print("(");
  33.             print(l, bestCut[l][r], bestCut);
  34.             System.out.print(" x ");
  35.             print(bestCut[l][r] + 1, r, bestCut);
  36.             System.out.print(")");
  37.         }
  38.     }
  39.     public static void main(String[] args) {
  40.         Scanner sc = new Scanner(System.in);
  41.         for (int c = 1, n = sc.nextInt(); n != 0; n = sc.nextInt(), c++) {
  42.             long[][] dp = new long[n][n];
  43.             for (int i = 0; i < n; i++) {
  44.                 for (int j = 0; j < n; j++) {
  45.                     dp[i][j] = Long.MAX_VALUE;
  46.                 }
  47.             }
  48.             Matrix[] sizes = new Matrix[n];
  49.             int[][] bestCut = new int[n][n];
  50.             for (int i = 0; i < n; i++) {
  51.                 for (int j = 0; j < n; j++) {
  52.                     bestCut[i][j] = Integer.MAX_VALUE;
  53.                 }
  54.             }
  55.             for (int i = 0; i < n; i++) {
  56.                 int width = sc.nextInt();
  57.                 int height = sc.nextInt();
  58.                 sizes[i] = new Matrix(width, height);
  59.             }
  60.             for (int i = 0; i < n; i++) {
  61.                 dp[i][i] = 0;
  62.             }
  63.             multiple(dp, sizes, bestCut, 0, n-1);
  64.             System.out.print("Case " + c + ": ");
  65.             print(0, n - 1, bestCut);
  66.             System.out.println();
  67.         }
  68.     }
  69. }
Runtime error #stdin #stdout #stderr 0.08s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.NoSuchElementException
	at java.util.Scanner.throwFor(Scanner.java:862)
	at java.util.Scanner.next(Scanner.java:1485)
	at java.util.Scanner.nextInt(Scanner.java:2117)
	at java.util.Scanner.nextInt(Scanner.java:2076)
	at Main.main(Main.java:41)
https://ideone.com/DIXVp2
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!