fork(1) download
copy 
  1. import java.util.Arrays;
  2.  
  3. public class Main {     
  4.     static double[] a = {20.0, 19.6, 19.2};
  5.     static double[] b = {22.454, 22.224, 21, 20.3, 19.9, 19, 18};
  6.     static boolean[][] takes;
  7.     static double INF = 1000.0;
  8.     static double[][] dp;
  9.  
  10.     public static void main(String[] args){
  11.         dp = new double[a.length][b.length];
  12.         takes = new boolean[a.length][b.length];
  13.  
  14.         for(int i=0; i<dp.length; i++){
  15.             Arrays.fill(dp[i], Double.MAX_VALUE);
  16.         }
  17.         System.out.println(maxMatching(a.length-1, b.length-1));
  18.         printSolution(a.length-1, b.length-1);
  19.     }
  20.  
  21.     static void printSolution(int i, int j){
  22.         if(i==-1 || j==-1){
  23.             return;
  24.         }
  25.         if(takes[i][j]){
  26.             System.out.println(a[i] + " " + b[j]);
  27.             printSolution(i-1, j-1);
  28.         }else{
  29.             printSolution(i, j-1);
  30.         }
  31.     }
  32.  
  33.     static double maxMatching(int i, int j){
  34.         if(i==-1){
  35.             return 0;
  36.         }
  37.         if(j==-1){
  38.             return INF;
  39.         }
  40.         if(dp[i][j] != Double.MAX_VALUE){
  41.             return dp[i][j];
  42.         }
  43.         double val1 = maxMatching(i, j-1);
  44.         double val2 = Math.abs(a[i] - b[j]) + maxMatching(i-1, j-1);
  45.         if(Double.compare(val1, val2)>0){
  46.             dp[i][j] = val2;
  47.             takes[i][j] = true;
  48.         }else{
  49.             dp[i][j] = val1;
  50.         }
  51.         return dp[i][j];
  52.     }
  53. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.7999999999999972
19.2 19.0
19.6 19.9
20.0 20.3
https://ideone.com/P0naEV
language:
Java (HotSpot 12)
created:
11 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!