fork download
copy 
  1. #include<stdio.h>
  2. #include<string.h>
  3.  
  4. #define MAXN 5005
  5.  
  6. int dp[MAXN][MAXN], inf = 1000000000;
  7.  
  8. int main() {
  9.     int n, a[MAXN],i,j;
  10. 	scanf("%d", &n);
  11. 	for(i = 1; i <= n; i++) {
  12. 		scanf("%d", &a[i]);
  13. 	}
  14.  
  15. 	for(i = 0; i <= n; i++) {
  16. 		for(j = 0; j <= n; j++) {
  17. 			dp[i][j] = inf;
  18. 		}
  19. 	}
  20. 	dp[0][0] = 0;
  21.  
  22. 	for(i = 1; i <= n; i++) {
  23. 		int k = -1, s = 0;
  24. 		for(j = i; j <= n; j++) {
  25. 			s += a[j];
  26. 			while(k+1<=n && dp[i-1][k+1] <= s) {
  27. 				k++;
  28. 			}
  29.  
  30. 			if(k>=0 && dp[j][k+1]>s) {
  31. 				dp[j][k+1]=s;
  32. 			}
  33. 		}
  34.  
  35. 		for(k = n-1; k >= 0; k--) {
  36. 			if(dp[i][k]>dp[i][k+1]) {
  37. 				dp[i][k]=dp[i][k+1];
  38. 			}
  39. 		}
  40. 	}
  41.  
  42. 	int res = inf,k;
  43. 	for(k = 1; k <= n; k++) {
  44. 		if(dp[n][k] < inf) {
  45. 			res = k;
  46. 		}
  47. 	}
  48.  
  49. 	printf("%d\n", n-res);
  50. }
Success #stdin #stdout 0s 99648KB
comments (?)
stdin
copy 
5
8 2 7 3 1
stdout
copy 
3
https://ideone.com/o7VMjy
language:
C (gcc 8.3)
created:
11 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!