经典BRT问题

解题思路:

注意事项:

参考代码:

import java.util.Scanner;
public class 公交汽车 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner=new Scanner(System.in);
  int [] m=new int [10];      //费用
  for (int i = 0; i < m.length; i++) {
m[i]=scanner.nextInt();
}
  int n=scanner.nextInt();   //总路程
  int [][] arr=new int [10][n+1];    //装没一公里的钱
  for (int i = 0; i < arr[0].length; i++) {
arr[0][i]=i*m[0];           //初始化  每重新开始一公里重新算钱
}
      for (int i = 1; i < arr.length; i++) {
      for (int j = 0; j < arr[i].length; j++) {
if (i+1<=j) {     //下一公里的钱小于等于本公里的钱
arr[i][j]=Math.min(arr[i-1][j], arr[i][j-i-1]+m[i]);//求公里花费最少的
}else {
arr[i][j]=arr[i-1][j];
}
}
}
      System.out.println(arr[9][n]);
}
}