Submission #1403465

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a) for(auto &i:a)
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/



typedef long long ll;
#define INF 1LL<<60
int N, W[4010];
ll dp[4010][4010];
int K[4010][4010];
ll sm[4010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> W[i];

    sm[0] = W[0];
    rep(i, 1, N) sm[i] = sm[i - 1] + W[i];
    rep(i, 0, N) rep(j, 0, N) dp[i][j] = INF;

    rep(len, 1, N + 1) {
        rep(L, 0, N - len + 1) {
            int R = L + len - 1;
            
            if (L == R) {
                dp[L][R] = 0;
                K[L][R] = L;
            } else {
                int mi = K[L][R - 1], ma = K[L + 1][R];
                dp[L][R] = INF;
                rep(i, mi, ma + 1) if (dp[L][i] + dp[i + 1][R] < dp[L][R]) {
                    dp[L][R] = dp[L][i] + dp[i + 1][R];
                    K[L][R] = i;
                }
                dp[L][R] += sm[R];
                if (0 < L) dp[L][R] -= sm[L - 1];
            }
        }
    }

    printf("%lld\n", dp[0][N - 1]);
}

Submission Info

Judge Result