1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 0x7fffffffffffffff
#define mem(a, x) memset(a,x,sizeof(a))
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef std::pair<int, int> Pii;
typedef std::pair<ll, ll> Pll;
ll power(ll a, ll b,ll p) { ll res = 1; for (; b > 0; b >>= 1) { if (b & 1) res = res * a % p; a = a * a % p; } return res; }
ll gcd(ll p, ll q) { return q == 0 ? p : gcd(q, p % q); }
ll _abs(ll x){return x < 0 ? -x : x;}
using namespace std;
int a[120],sum[120];
int dp[120][120];
int main(){
io_opt;
int n;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=10000000;
}
dp[i][i]=0;
}
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1],dp[i][j]);
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}
|