Submission #691665

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define FORR(i,a,b) for (int i=a; i>=b; i--)
#define pi M_PI

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> PII;

int n;
VI w, s;
int dp[3001][3001], p[3001][3001];

int rec(int i, int j){
    if (dp[i][j]>0)
        return dp[i][j];

    if (i==j){
        p[i][i] = i;
        return dp[i][j] = 0;
    }

    int m = 1e8;
    rec(i,j-1);
    rec(i+1,j);
    FOR(k,p[i][j-1],max(j,p[i+1][j])-1){
        int d = rec(i,k)+rec(k+1,j);
        if (d<m){
            p[i][j] = k;
            m = d;
        }
    }
    m += s[j+1]-s[i];

    return dp[i][j] = m;
}

int main(void){
    int n;
    cin >> n;
    if (n>3000)
        return 0;
    w.resize(n);
    s.resize(n+1);
    REP(i,n){
        cin >> w[i];
        s[i+1] = s[i]+w[i];
    }

    cout << rec(0,n-1) << endl;

    return 0;
}

Submission Info

Judge Result