题解 | 合并

区间dp

#include <iostream>
#include<bits/stdc++.h>
#include <vector>
using namespace std;

int main() {
    // int a, b;
    // while (cin >> a >> b) { // 注意 while 处理多个 case
    //     cout << a + b << endl;
    // }
    int n;
    cin>>n;
    vector<int> a(n+1,0);
    vector<int> prefixSum(n+1,0);
    for(int i=0;i<n;++i)
    {
        cin>>a[i+1];
        prefixSum[i+1]=prefixSum[i]+a[i+1];
        // cout<<prefixSum[i+1]<<" ";
    }
    vector<vector<long long>> dp(n+1,vector<long long>(n+1,0));
    for(int len=2;len<=n;++len)
    {
        for(int start=1;start+len-1<=n;++start)
        {
            if(len==2)dp[start][start+len-1]=a[start]*a[start+len-1];
            for(int mid=start;mid<start+len-1;++mid)
            {
                dp[start][start+len-1]=max(dp[start][mid]+dp[mid+1][start+len-1]+(prefixSum[mid]-prefixSum[start-1])*(prefixSum[start+len-1]-prefixSum[mid]),dp[start][start+len-1]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")