fork download
copy 
  1. import java.util.*;
  2.  
  3. public class Main {
  4.  
  5.     static final long INF = (long) 1e18;
  6.  
  7.     public static void main(String[] args) {
  8.  
  9.         Scanner sc = new Scanner(System.in);
  10. 		int n = sc.nextInt();
  11.  
  12.         long[] a = new long[n + 1];
  13. 		for (int i = 1; i <= n; i++) {
  14.             a[i] = sc.nextLong();
  15.         }
  16.  
  17.         long[][] dp = new long[n + 1][101];
  18.         for (int i = 0; i <= n; i++) {
  19.             Arrays.fill(dp[i], INF);
  20.         }
  21.  
  22.         // Khali prefix
  23.         dp[0][0] = 0;
  24. 		for (int i = 1; i <= n; i++) {
  25.             long sum = 0;
  26.             // Akhari block = A[j ... i]
  27.             for (int j = i; j >= 1; j--) {
  28.                 sum += a[j];
  29.                 if (sum > 100) {
  30.                     break;
  31.                 }
  32.                 int cost = i - j;
  33.                 // Pichla block sum
  34.                 for (int previousSum = 0;
  35.                      previousSum <= sum;
  36.                      previousSum++) {
  37.  
  38.                     if (dp[j - 1][previousSum] == INF) {
  39.                         continue;
  40.                     }
  41.  
  42.                     dp[i][(int) sum] = Math.min(
  43.                         dp[i][(int) sum],
  44.                         dp[j - 1][previousSum] + cost
  45.                     );
  46.                 }
  47.             }
  48.         }
  49.  
  50.         long answer = INF;
  51.  
  52.         for (int lastSum = 0; lastSum <= 100; lastSum++) {
  53.             answer = Math.min(answer, dp[n][lastSum]);
  54.         }
  55.  
  56.         System.out.println(answer);
  57.     }
  58. }
  59.  
Success #stdin #stdout 0.17s 54544KB
comments (?)
stdin
copy 
5
2 4 1 6 12
stdout
copy 
1
https://ideone.com/V0qNMZ
Visa OA - 2027/2028 Grads
language:
Java (HotSpot 12)
created:
18 hours 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!