Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- __________.__ .__ .____
- \______ \__| ____ | |__ | | ____
- | | _/ |/ \| | \ | | _/ __ \
- | | \ | | \ Y \ | |__\ ___/
- |______ /__|___| /___| / |_______ \___ >
- \/ \/ \/ \/ \/
- */
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long llu;
- #define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- #define val first
- #define pos second
- #define mp make_pair
- #define TASK "cf"
- #define pb push_back
- #define ep emplace_back
- #define sz(a) (int) a.size()
- #define FOR(x,a,b) for (ll x=a,u;x<=b;x++)
- #define FOD(x,a,b) for (int x=a;x>=b;x--)
- #define REP(x,a,b) for (int x=a;x<b;x++)
- #define RED(x,a,b) for (int x=a;x>b;x--)
- #define EL cout<<endl
- #define vi vector<int>
- #define vii vector<vi>
- #define pii pair<ll,ll>
- #pragma GCC optimize("Ofast")
- void init(){
- freopen(TASK".inp","r",stdin);
- freopen(TASK".out","w",stdout);
- }
- const long long N = 200001;
- const long long mod = 100;
- ll pos, n, mi[N], ma[N], k;
- ll a[N],cnt[N],ans,_;
- ll mau[245][245];
- ll f[245][245];
- ll ps[245];
- int main(){
- IO
- init();
- cin >> n;
- FOR(i,1,n){
- cin >> a[i];
- ps[i] = (ps[i-1] + a[i]);
- }
- FOR(i,1,n){
- FOR(j,1,n){
- f[i][j] = INT_MAX;
- }
- }
- FOR(i,1,n)f[i][i] = 0;
- FOR(len,2,n){
- FOR(i,1,n){
- int j = i+len-1;
- if(j > n) break;
- FOR(k,i,j-1){
- f[i][j] = min( f[i][j], f[i][k] * f[k+1][j] + (ps[j] - ps[i-1]) );
- }
- }
- }
- cout << f[1][n];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement