题解 | #加分二叉树#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param scores int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<int> getpre(int l, int r, vector<vector<int>> &res){
        vector<int> pre;
        if(l > r)return pre;
        int root = res[l][r];
        pre.push_back(root);
        vector<int> left = getpre(l, root-1, res);
        pre.insert(pre.end(), left.begin(), left.end());
        vector<int> right = getpre(root+1, r, res);
        pre.insert(pre.end(), right.begin(), right.end());
        return pre;
    }
    vector<vector<int> > scoreTree(vector<int>& scores) {
        int n = scores.size();
        vector<vector<int>> rmap(n, vector<int>(n, 0));
        vector<vector<int>> res(n, vector<int>(n, 0));
        for(int i = 0; i < n ;i ++){
            rmap[i][i] = scores[i];
            res[i][i] = i;
        }
        for(int l = 1; l < n; l++){
            for(int i = 0; i + l < n; i++){
                int tmpscore = rmap[i][i+l];
                for(int k = i; k <= i + l; k++){
                    if(k == i){
                        tmpscore = rmap[k+1][i+l] + scores[i];
                    }
                    else if(k == i+l){
                        tmpscore = rmap[i][i+l-1] + scores[k];
                    }
                    else{
                        tmpscore = rmap[i][k-1] * rmap[k+1][i+l] + scores[k];
                    }
                    if(tmpscore > rmap[i][i+l]){
                        rmap[i][i+l] = tmpscore;
                        res[i][i + l] = k;
                    }
                }
            }
        }
        vector<vector<int> > ans;
        vector<int> maxscore;
        maxscore.push_back(rmap[0][n-1]);
        ans.push_back(maxscore);
        vector<int> pre = getpre(0, n-1, res);
        for(int i = 0; i < n ;i++)pre[i]++;
        ans.push_back(pre);
        return ans;
    }
};