1485 Fast Food

「1485 Fast Food」の編集履歴（バックアップ）一覧はこちら

「1485 Fast Food」(2006/05/14 (日) 00:19:51) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1485 Fast Food
**解答例
 import java.util.*;
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int cnt = 0;
         while(true){
             int n = sc.nextInt();
             int k = sc.nextInt();
             if(n==0&&k==0) break;
             
             int[] x = new int[n];
             for(int i=0;i<n;i++){
                 x[i] = sc.nextInt();
             }
             Solver sol = new Solver(n, k, x);
             int[] ans = sol.solve();
             
             System.out.printf("Chain %d\r\n",cnt+1);
             for(int i=0;i<k;i++){
                 int start = ans[i]+1;
                 int end = ans[i+1];
                 int center = (start+end)/2;
                 if(start!=end){
                     System.out.printf("Depot %d at restaurant %d serves restaurants %d to %d\r\n", i+1, center, start, end);
                 }
                 else{
                     System.out.printf("Depot %d at restaurant %d serves restaurant %d\r\n", i+1, center, start);
                 }
             }
             System.out.printf("Total distance sum = %d\r\n", ans[k+1]);
             System.out.println();
         }
     }
 }
 
 class Solver{
     int n;
     int k;
     int x[];
     public Solver(int n, int k, int[] x) {
         this.n = n;
         this.k = k;
         this.x = x;
     }
     public int[] solve(){
         int[] ret = new int[k+2];
         
         int[][] w = new int[n][n];
         for(int i=0;i<n;i++){
             for(int j=i;j<n;j++){
                 int c = (i+j)/2;
                 int sum = 0;
                 for(int m=i;m<=j;m++) sum += Math.abs(x[m]-x[c]);
                 w[i][j] = sum;
             }
         }
         
         int[][] t = new int[n][k];
         int[][] s = new int[n][k];
         for(int i=0;i<n;i++){
             t[i][0] = w[0][i];
             s[i][0] = 0;
         }
         for(int j=1;j<k;j++){
             t[j][j] = 0;
             s[j][j] = j;
             for(int i=j+1;i<n;i++){
                 int min = Integer.MAX_VALUE;
                 for(int m=j;m<=i;m++){
                     int sum = t[m-1][j-1] + w[m][i];
                     if(sum<min){
                         min = sum;
                         t[i][j] = min;
                         s[i][j] = m;
                     }
                 }
             }
         }
         ret[k+1] = t[n-1][k-1];
         ret[k] = n;
         for(int i=k-1;i>=0;i--){
             ret[i] = s[ret[i+1]-1][i];
         }
         return ret;
     }
 }