fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. int a[1006];
  5. int s[1007];
  6. int f[1008][1009];
  7.  
  8. int main() {
  9. freopen("stones.INP", "r", stdin);
  10. freopen("stones.OUT", "w", stdout);
  11. cin>>n;
  12. for (int i=1;i<=n;i++)
  13. {
  14. cin>>a[i];
  15. s[i]=s[i-1]+a[i];
  16. }
  17.  
  18. for (int i=1;i<=n;i++) {
  19. f[i][i]=0;
  20. }
  21. for (int len=2;len<=n;len++) {
  22. for (int i=1;i+len-1<=n;i++) {
  23. int j=i+len-1;
  24. f[i][j] = INT_MAX;
  25. for (int k=i;k<j;k++) {
  26. f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
  27. }
  28. }
  29. }
  30. cout<<f[1][n];
  31. return 0;
  32. }
  33.  
  34.  
Success #stdin #stdout 0.01s 5268KB
stdin
Standard input is empty
stdout
Standard output is empty