首页 > 专题系列 > Java解POJ > POJ 1695 Magazine Delivery [解题报告] Java
2013
11-10

POJ 1695 Magazine Delivery [解题报告] Java

Magazine Delivery

问题描述 :

The TTT Taxi Service in Tehran is required to deliver some magazines to N locations in Tehran. The locations are labeled L1 to LN. TTT assigns 3 cars for this service. At time 0, all the 3 cars and magazines are located at L1. There are plenty of magazines available in L1 and the cars can take as many as they want. Copies of the magazine should be delivered to all locations, observing the following rules:
  1. For all i = 2 .. N, magazines should be delivered at Li only after magazines are delivered at Li-1 .
  2. At any time, only one of the three cars is driving, and the other two are resting in other locations.

The time to go from Li to Lj (or reverse) by any car is a positive integer denoted by D[i , j].

The goal is to organize the delivery schedule for the cars such that the time by which magazines are delivered to all N locations is minimum.

Write a program to compute the minimum delivery time.

输入:

The input file contains M instances of this problem (1 <= M <= 10). The first line of the input file is M. The descriptions of the input data follows one after the other. Each instance starts with N in a single line (N <= 30). Each line i of the following N-1 lines contains D[i , j], for all i=1..N-1, and j=i+1..N.

输出:

The output contains M lines, each corresponding the solution to one of the input data. In each line, the minimum time it takes to deliver the magazines to all N locations is written.

样例输入:

1
5
10 20 3 4
5 10 20
8 18
19

样例输出:

22

解题代码:

/* @author:zeropinzuo */
import java.io.*;
import java.util.*;

public class Main{
 static Scanner cin;
 public static void main(String args[]){
  cin  = new Scanner(System.in);
  int M = cin.nextInt();
  for(int i=0;i< M;i++)
   run();
  }
	
  static void run(){
    int N = cin.nextInt();
    int[][] d = new int[N+1][N+1];
    for(int i=1;i< N;i++)
     for(int j=i+1;j<=N;j++)
	d[i][j] = cin.nextInt();
	
    int[][][] f = new int[N+1][N+1][N+1];
    for(int i=1;i<=N;i++)//初始化
      for(int j=1;j<=N;j++)
        for(int k=1;k<=N;k++)
           f[i][j][k]=10000;
    f[1][1][1] = 0;
    for(int k=2;k<=N;k++)
      for(int i=1;i< k;i++)
	for(int j=1;j< k;j++){
	  if(f[i][j][k-1]+d[i][k]< f[j][k-1][k]){
	   f[j][k-1][k]=f[i][j][k-1]+d[i][k];
	   f[k-1][j][k]=f[i][j][k-1]+d[i][k];
	  }
	  if(f[i][j][k-1]+d[j][k]< f[i][k-1][k]){
	    f[i][k-1][k]=f[i][j][k-1]+d[j][k];
	    f[k-1][i][k]=f[i][j][k-1]+d[j][k];
	   }
	  if(f[i][j][k-1]+d[k-1][k]< f[i][j][k]){
	    f[i][j][k]=f[i][j][k-1]+d[k-1][k]; 
	    f[j][i][k]=f[i][j][k-1]+d[k-1][k];
	  }
	} 
		
    int opt=f[1][1][N];
    for(int i=1;i< N;i++)
      for(int j=1;j< N;j++)
        if(f[i][j][N]< opt)
          opt=f[i][j][N];
    System.out.println(opt);
  }
}

  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的