Subtask ~2~ ~(1 \le N \le 100)~

• Gọi ~dp[i][j]~ là số điểm cao nhất mà ~PiuPiu~ có thể đạt được trên đoạn ~[i, j]~.
• Gọi ~Val = min(dp[i][k] + sum[i][k], dp[k + 1][j] + sum[k + 1][j])~ là phần có điểm ít hơn mà ~PiuPiu~ được chọn khi lấy ~k~ làm điểm chia ~(i \le k < j)~.
• Ta có công thức truy hồi: ~dp[i][j] = max(dp[i][j], Val)~
• Đpt: ~O(n^3)~

Code tham khảo của dinhwe2612

#include <bits/stdc++.h>
#define F first
#define S second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1LL)

typedef long long ll;

using namespace std;

const int N = 2002;

int n, a[N], dp[N][N], sum[N];
int Sum(int l, int r) {
    return sum[r] - sum[l - 1];
}

int main() {

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i], sum[i] = sum[i - 1] + a[i];
    for(int i = n; i >= 1; --i) {
        for(int j = i; j <= n; ++j) {
            if (i == j) dp[i][j] = 0;
            else {
                dp[i][j] = 0;
                for(int k = i; k < j; ++k) {
                    dp[i][j] = max(dp[i][j], min(dp[i][k] + Sum(i, k), dp[k + 1][j] + Sum(k + 1, j)));
                }
            }
        }
    }
    cout << dp[1][n];

    return 0;
}

Subtask ~3~ ~(n \le 2000)~

• Áp dụng tư tưởng knuth - optimization, ta thấy rằng, với mỗi cặp ~i, j~ ta chỉ cần duyệt ~k~ từ những giá trị ~k~ đã tối ưu của đoạn ~[i, j-1]~ và ~[i +1, j]~, vậy mỗi cặp ~i, j~ đã được duyệt ta lưu lại giá trị ~k~ đã tối ưu vào một mảng ~pos~ và dùng lại ở cấu hình tiếp theo.
• Đpt: ~O(n^2)~.

Code tham khảo của kieuphat159

                    // Template \\
#include <bits/stdc++.h>
#define FOR(i, a, b) for(ll i=a, _b=b; i<=_b; i++)

using namespace std;
typedef int64_t ll;
const ll maxn = 2e3 + 2;

template<class T>
    bool maximize(T &a, T b){
        return a<b ? a=b, true : false;
    }

                    // Main Function //

ll n, a[maxn], f[maxn][maxn], pos[maxn][maxn];;

void input()
{
    cin>>n;
    FOR(i, 1, n) cin>>a[i], a[i] += a[i-1];
}

void solve()
{
    FOR(i, 1, n) pos[i][i] = i;

    FOR(len, 1, n)
        FOR(i, 1, n-1)
        {
            ll j = i + len;
            for(ll k = max(i, pos[i][j - 1]); k <= pos[i + 1][j] && k < j; k++) 
            {
                ll val = min(a[k] - a[i - 1] + f[i][k], a[j] - a[k] + f[k + 1][j]);
                if (maximize(f[i][j], val)) 
                    pos[i][j] = k;
            }
        }
    cout<<f[1][n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #define task ""
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);
    int test_case=1; //cin>>test_case;
    while(test_case--)
    {
        input(), solve();
        cout<<'\n';
    }
    return 0;
}