P1040 加分二叉树

樹上dp

枚舉從 l -> r 中的點做頂點下的左右子樹的分數， dp找每次最大的分數

dfs(l, k-1)*dfs(k+1, r) + f[k][k]; // k 為 根節點時， l，k-1 為左子樹  k+1，r 右子樹

#include <bits/stdc++.h>
using namespace std;
#define _for(i,a,b) for(int i = (a); i < (b); i++)
#define _rep(i,a,b) for(int i = (a); i <= (b); i++)
#define ll long long
int n, f[40][40], root[40][40];
bool flag = true;
int dfs(int l, int r){
    int sum = 0;
    if(l > r) return 1;// 空子樹
    if(!f[l][r]){
        _rep(k,l,r)
        {
            sum = dfs(l, k-1)*dfs(k+1, r) + f[k][k];//狀態轉移
            if(sum > f[l][r])
                f[l][r] = sum, root[l][r] = k;
        }
    }
    return f[l][r];
}
void printfront(int l, int r){
    if(l > r) return ;
    if(flag) flag = false;
    else cout << " ";
    cout << root[l][r];
    printfront(l, root[l][r]-1);// 根 左子樹  右子樹
    printfront(root[l][r]+1, r);
}
void solve(){
    cin >> n;
    memset(f, 0, sizeof(f));
    _rep(i,1,n) cin >> f[i][i], root[i][i] = i;
    cout << dfs(1, n) << endl;
    printfront(1, n);
}

int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    //freopen("output.txt", "w", stdout);
    solve();
    return 0;
}