fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xlzoIW
language:
C++14 (clang 8.0)
created:
1 day 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!