Guest User

Untitled

a guest
Feb 4th, 2018
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.20 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5.  
  6. /**
  7.  * Created by bugkiller on 04/02/18.
  8.  */
  9. class SUPW {
  10.  
  11.     static int a[] = new int[200000];
  12.     static int dp[] = new int[200000];
  13.  
  14.     public static void main(String[] args) throws IOException {
  15.  
  16.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  17.         int n;
  18.         String[] s;
  19.         n = Integer.parseInt(br.readLine());
  20.         s = br.readLine().split("\\s");
  21.         for (int i = 0; i < n; i++) {
  22.             a[i] = Integer.parseInt(s[i]);
  23.         }
  24.         System.out.println(solve(a, n));
  25.     }
  26.  
  27.     private static int solve(int[] a, int n) {
  28.         Arrays.fill(dp, 0, n, 0);
  29.         return minimumTime(a, dp, n);
  30.     }
  31.  
  32.     private static int minimumTime(int[] a, int[] dp, int n) {
  33.         if (n <= 2) {
  34.             return 0;
  35.         }
  36.         dp[0] = a[0];
  37.         dp[1] = a[1];
  38.         dp[2] = a[2];
  39.         for (int i = 3; i < n; i++) {
  40.             dp[i] = a[i] + Integer.min(Integer.min(dp[i - 1], dp[i - 2]), dp[i - 3]);
  41.         }
  42.         return Integer.min(Integer.min(dp[n - 1], dp[n - 2]), dp[n - 3]);
  43.     }
  44.  
  45. }
Add Comment
Please, Sign In to add comment