fork(13) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone
  6. {
  7. 	public static void main (String[] args) throws java.lang.Exception
  8. 	{
  9. 		System.out.println(calculateMinCost(new int[] { 1,4,6,7,28,30 }));
  10. 		System.out.println(calculateMinCost(new int[] { 1,7,8,9,10 }));
  11. 		System.out.println(calculateMinCost(new int[] { 1,7,8,9,10,15 }));
  12. 	}
  13.  
  14. 	public static int calculateMinCost(int[] arr) {
  15. 		boolean[] isDayWithTrip = new boolean[31]; // note: initializes to false
  16. 		for (final int dayWithTrip : arr) {
  17. 		    isDayWithTrip[dayWithTrip] = true;
  18. 		}
  19.  
  20. 		int[] minCostUpThroughDay = new int[31];
  21. 		minCostUpThroughDay[0] = 0; // technically redundant
  22. 		for (int d = 1; d <= 30; ++d) {
  23. 		    if (! isDayWithTrip[d]) {
  24. 		        minCostUpThroughDay[d] = minCostUpThroughDay[d-1];
  25. 		        continue;
  26. 		    }
  27.  
  28. 		    int minCost;
  29. 		    // Possibility #1: one-day pass on day d:
  30. 		    minCost = minCostUpThroughDay[d-1] + 2;
  31. 		    // Possibility #2: seven-day pass ending on or after day d:
  32. 	        minCost =
  33. 	        	Math.min(minCost, minCostUpThroughDay[Math.max(0, d-7)] + 7);
  34. 		    // Possibility #3: 30-day pass for the whole period:
  35. 		    minCost = Math.min(minCost, 25);
  36.  
  37. 		    minCostUpThroughDay[d] = minCost;
  38. 		}
  39.  
  40. 		return minCostUpThroughDay[30];
  41. 	}
  42. }
Success #stdin #stdout 0.04s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
11
9
11
https://ideone.com/1Xx1fd
language:
Java (HotSpot 12)
created:
6 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!