一种树形dp的状态设计及树型结构表示法。
其中$dp[l][r]$表示编号$l\to r$节点的最大加分,$root[l][r]$表示编号$l\to r$节点的根。
自顶向下递归求解。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 31;
int n;
int credit[MAXN];
ll dp[MAXN][MAXN];
ll root[MAXN][MAXN];
ll search(int l, int r) {
int now;
if ( l > r )
return 1;
if ( dp[l][r] == -1 )
for ( int i = l; i <= r; ++i ) {
now = search(l, i - 1) * search(i + 1, r) + dp[i][i];
if( now > dp[l][r] ) {
dp[l][r] = now;
root[l][r] = i;
}
}
return dp[l][r];
}
void printtree(int l, int r) {
if ( l > r )
return;
cout << root[l][r] << ' ';
printtree(l, root[l][r] - 1);
printtree(root[l][r] + 1, r);
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for ( int i = 1; i <= n; ++i )
for ( int j = i; j <= n; ++j )
dp[i][j] = -1;
for ( int i = 1; i <= n; ++i ) {
cin >> dp[i][i];
root[i][i] = i;
}
cout << search(1, n) << endl;
printtree(1, n);
return 0;
}