fork download
  1. #include<iostream>
  2. #include<cstdio>
  3.  
  4. const int MAX_N = 8000, MAX_G = 800;
  5. const long long INF = 1ll<<62;
  6. int N,G;
  7. long long s[MAX_N+10];
  8. struct {long long val; int opt;} dp[MAX_N+10][MAX_G+10];
  9.  
  10. inline long long cost(int l, int r) { return (s[r]-s[l-1])*1ll*(r-l+1); }
  11.  
  12. int main()
  13. {
  14. scanf("%d%d\n", &N, &G);
  15. for (int i = 1; i <= N; ++i)
  16. {
  17. scanf("%d\n", s+i);
  18. s[i] += s[i-1];
  19. }
  20. if (N <= G)
  21. {
  22. printf("%lld", s[N]);
  23. return 0;
  24. }
  25.  
  26. for (int i = 1; i <= N; ++i)
  27. {
  28. dp[i][i].val = s[i];
  29. dp[i][i].opt = std::max(i-1, 1);
  30.  
  31. dp[i][1].val = i*s[i];
  32. dp[i][1].opt = 1;
  33. }
  34.  
  35. for (int i = 2; i <= N; ++i)
  36. for (int j = std::min(G, i-1); j > 1 ; --j)
  37. {
  38. dp[i][j].val = INF;
  39.  
  40. int to = j==G?i-1:dp[i][j+1].opt;
  41. for (int k = dp[i-1][j].opt; k <= to; ++k)
  42. {
  43. long long val = dp[k][j-1].val + cost(k+1, i);
  44. if (dp[i][j].val > val)
  45. {
  46. dp[i][j].val = val;
  47. dp[i][j].opt = k;
  48. }
  49. }
  50. }
  51.  
  52. printf("%lld", dp[N][G].val);
  53. }
Success #stdin #stdout 0s 79552KB
stdin
Standard input is empty
stdout
Standard output is empty