Submission #6136775

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
const int MAX = 4040;
using ll = long long;
ll dp[MAX][MAX];
int ar[MAX][MAX];
signed main(){
  int n;
  cin>>n;
  vector<ll> ws(n);
  for(int i=0;i<n;i++) cin>>ws[i];

  vector<ll> sm(n+1,0);
  for(int i=0;i<n;i++) sm[i+1]=sm[i]+ws[i];

  for(int i=0;i<n;i++){
    dp[i][i]=0;
    ar[i][i]=i;
  }

  for(int w=1;w<n;w++){
    for(int i=0;i+w<n;i++){
      int j=i+w;
      int p=ar[i][j-1];
      int q=ar[i+1][j];
      dp[i][j]=dp[i][p]+dp[p+1][j];
      ar[i][j]=p;
      for(int k=p;k<=q;k++){
        ll res=dp[i][k]+dp[k+1][j];
        if(res<dp[i][j]){
          dp[i][j]=res;
          ar[i][j]=k;
        }
      }
      dp[i][j]+=sm[j+1]-sm[i];
    }
  }

  cout<<dp[0][n-1]<<endl;
  return 0;
}

Submission Info

Judge Result