分离与合体

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1573 字

把[1,n]不断在内部点分离成两段直到单点，

一本通
练习

正文

/*
原题：分离与合体（区间 DP 求最大价值并输出分离点序列）
题意：把 [1,n] 不断在内部点分离成两段直到单点，合体时得 (两端点权值和)×分离点权值，求最大总价值及分离序列。
思路：dp[l][r]=max{(a[l]+a[r])*a[k]+dp[l][k]+dp[k+1][r]}（k 为分离点）；
      记录每个区间最优且最靠左的分离点，按层序（从左到右）输出所有内部分离点。
复杂度：时间 O(n^3)，空间 O(n^2)
易错点：分离点不能是区间端点本身（k∈[l,r-1]）；多解时取最靠左的 k 保证字典序最小。
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<long long> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<vector<long long>> dp(n+1, vector<long long>(n+1,0));
    vector<vector<int>> sp(n+1, vector<int>(n+1,0));
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            long long best=-1;
            int bestk=0;
            for(int k=l;k<r;k++){
                long long val=(a[l]+a[r])*a[k]+dp[l][k]+dp[k+1][r];
                if(val>best){
                    best=val;
                    bestk=k;
                }
            }
            dp[l][r]=best;
            sp[l][r]=bestk;
        }
    }
    cout<<dp[1][n]<<"\n";
    vector<int> order;
    queue<pair<int,int>> q;
    q.push({1,n});
    while(!q.empty()){
        int sz=q.size();
        while(sz--){
            auto [l,r]=q.front();
            q.pop();
            if(r-l<1) continue;
            int k=sp[l][r];
            order.push_back(k);
            if(k-l>=1) q.push({l,k});
            if(r-(k+1)>=1) q.push({k+1,r});
        }
    }
    for(size_t i=0;i<order.size();i++){
        if(i) cout<<" ";
        cout<<order[i];
    }
    cout<<"\n";
    return 0;
}

分离与合体

正文

一本通·提高篇的其它内容