提出 #758737

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
int n;
int a[3001],b[3001];

int mem[3001][3001];
int g[3001][3001];

int solve(int l,int r){
  if(mem[l][r])return mem[l][r];
  if(l==r){
    g[l][r]=l;
    return a[l];
  }
  int res=1e9;
  solve(l+1,r);
  solve(l,r-1);
  int si=max(l,g[l][r-1]);
  int ti=min(r-1,g[l+1][r]);
  
  for(int i=si;i<=ti;i++){
    int cost=solve(l,i)+solve(i+1,r);
    if(cost<res){
      res=cost;
      g[l][r]=i;
    }
  }
  
  return mem[l][r]=res+b[r]-b[l-1];
}

int main(){
  cin>>n;
  if(n>3001)return 0;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    b[i]=a[i]+b[i-1];
  }
  cout<<solve(1,n)-b[n]<<endl;
  return 0;
}

提出情報

ジャッジ結果