Aizu Online Judge 0145 Cards

■0145 Cards

動的計画法による解法．計算量はO(n)

dp[i][j]=i番目からj番目のカードをまとめたときの最小コスト
とすると，
dp[i][i]=0
dp[i][j]=min_k{dp[i][k]+dp[k+1][j]+a[i]*b[k]*a[k+1]*b[j]}
となる．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n;  
17.  int[] a, b;  
18.   
19.  void run(){  
20.   n=sc.nextInt();  
21.   a=new int[n];  
22.   b=new int[n];  
23.   for(int i=0; i<n; i++){  
24.    a[i]=sc.nextInt();  
25.    b[i]=sc.nextInt();  
26.   }  
27.   solve();  
28.  }  
29.   
30.  void solve(){  
31.   int[][] dp=new int[n][n];  
32.   
33.   for(int i=0; i<n; i++){  
34.    Arrays.fill(dp[i], INF);  
35.    dp[i][i]=0;  
36.   }  
37.   
38.   for(int m=1; m<n; m++){  
39.    for(int i=0, j=m; j<n; i++, j++){  
40.     for(int k=i; k<j; k++){  
41.      dp[i][j]=Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+a[i]*b[k]  
42.        *a[k+1]*b[j]);  
43.     }  
44.    }  
45.   }  
46.   
47.   println(""+dp[0][n-1]);  
48.   
49.  }  
50.   
51.  void debug(Object... os){  
52.   System.err.println(Arrays.deepToString(os));  
53.  }  
54.   
55.  void print(String s){  
56.   System.out.print(s);  
57.  }  
58.   
59.  void println(String s){  
60.   System.out.println(s);  
61.  }  
62.   
63.  public static void main(String[] args){  
64.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
65.   new Main().run();  
66.  }  
67. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 int[] a, b;

 void run(){
  n=sc.nextInt();
  a=new int[n];
  b=new int[n];
  for(int i=0; i<n; i++){
   a[i]=sc.nextInt();
   b[i]=sc.nextInt();
  }
  solve();
 }

 void solve(){
  int[][] dp=new int[n][n];

  for(int i=0; i<n; i++){
   Arrays.fill(dp[i], INF);
   dp[i][i]=0;
  }

  for(int m=1; m<n; m++){
   for(int i=0, j=m; j<n; i++, j++){
    for(int k=i; k<j; k++){
     dp[i][j]=Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+a[i]*b[k]
       *a[k+1]*b[j]);
    }
   }
  }

  println(""+dp[0][n-1]);

 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}