fork download
copy 
  1. #include<stdio.h>
  2. long long D[7][2212][2212];
  3. long long C[2121][2121];
  4. int P[7][2212][2212];
  5. int a[2121],b[2121];
  6. int main() {
  7. 	int n, k, i, j, p, q;
  8. 	scanf("%d%d", &n,&k);
  9. 	for (i = 0; i < n; i++)scanf("%d", &a[i]), a[n + i] = a[i];
  10. 	for (i = 0; i < 2 * n; i++) {
  11. 		for (j = i + 1; j < 2 * n; j++) {
  12. 			D[0][i][j] = C[i][j] = C[i][j - 1] + (j - i)*a[j];
  13. 		}
  14. 	}
  15. 	for (i = 1; i < k; i++) {
  16. 		for (j = 0; j + i < 2 * n; j++) P[i][j][j + i] = j;
  17. 		for (j = i + 2; j <= n; j++) {
  18. 			for (p = 0; j + p - 1 < 2 * n; p++) {
  19. 				int s = p, e = j + p - 1;
  20. 				D[i][s][e] = 1e18;
  21. 				for (q = P[i][s][e - 1]; q <= P[i][s + 1][e]; q++) {
  22. 					if (D[i][s][e] > C[s][q] + D[i - 1][q + 1][e])
  23. 						D[i][s][e] = C[s][q] + D[i - 1][q + 1][e], P[i][s][e] = q;
  24. 				}
  25. 			}
  26. 		}
  27. 	}
  28. 	long long ans = 1e18;
  29. 	for (i = 0; i + n - 1 < 2 * n; i++) {
  30. 		if (ans > D[k - 1][i][i + n - 1])ans = D[k - 1][i][i + n - 1];
  31. 	}
  32. 	printf("%lld", ans);
  33. 	return 0;
  34. }
Success #stdin #stdout 0s 4164KB
comments (?)
stdin
copy 
6 2
2
5
4
2
6
2
stdout
copy 
14
https://ideone.com/gHjf1f
language:
C++ (gcc 8.3)
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!