fork(11) download 
  1.  
  2. /**
  3.  * Created by aditya on 11/10/16.
  4.  */
  5.     class PublicTicketCost {
  6.         public static void main(String args[]){
  7.             int[] arr  =  {1,7,8,9,10,15,16,17,18,21,25};
  8.             int[] tDays = {1,7,30};
  9.             int[] tCost = {2,7,25};
  10.             System.out.println(minCost(arr, tDays, tCost));
  11.         }
  12.         public static int minCost(int[] arr, int[] tDays, int[] tCost) {
  13.             int[][] dp = new int[arr.length][tDays.length];
  14.  
  15.             for (int i = 0; i < arr.length; i++) {
  16.                 for (int j = 0; j < tDays.length; j++) {
  17.  
  18.                     int prevDayIndex = findPrevDayIndex(arr,i,tDays,j);
  19.                     int prevCost = prevDayIndex>=0 ? dp[prevDayIndex][tDays.length-1] : 0;
  20.                     int currCost = prevCost + tCost[j];
  21.                     if(j-1>=0){
  22.                         currCost = Math.min(currCost, dp[i][j-1]);
  23.                     }
  24.                     dp[i][j] = currCost;
  25.                 }
  26.             }
  27.             //print(dp);
  28.             return dp[arr.length-1][tDays.length-1];
  29.         }
  30.         private static void print(int arr[][]){
  31.             for (int i = 0; i < arr.length; i++) {
  32.                 for (int j = 0; j < arr[0].length; j++) {
  33.                     System.out.print(arr[i][j]+" ");
  34.                 }
  35.                 System.out.println();
  36.             }
  37.         }
  38.         private static int findPrevDayIndex(int[] arr, int i, int[] days, int j){
  39.             int validAfterDate = arr[i] - days[j];
  40.             if (validAfterDate<1){
  41.                 return -1;
  42.             }
  43.             for (int k = i-1; k >= 0; k--) {
  44.                 if (arr[k]<=validAfterDate){
  45.                     return k;
  46.                 }
  47.             }
  48.             return -1;
  49.         }
  50.     }
Success #stdin #stdout 0.05s 711168KB
comments (?)
stdin 
Standard input is empty
stdout 
18
https://ideone.com/sfgxGo
language:
Java (HotSpot 12)
created:
9 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!