[CODEVS 1090][NOIP 2013]プラス分岐ツリー(ツリーdp)

タイトルの説明
トランスファゲート
問題解
f[i][j][k]は、ノードj~kがiをルートとする最大加算点を表す.記憶化検索でやる.各区間のルートを記録し、出力を再帰します.
コード#コード#

#include
#include
#include
using namespace std;
#define LL long long
const int N=35;

int n; LL ans;
int root[N][N],ansroot[N][N];
LL score[N],f[N][N][N];

inline LL dfs(int now,int l,int r){
    if (f[now][l][r]!=-1) return f[now][l][r];
    if (l==r){
        f[now][l][r]=score[l];
        root[l][r]=l;
        return f[now][l][r];
    }
    LL lch=0,rch=0,t;
    for (int i=l;i<now;++i)
      if (lchnow-1))){
        lch=t;
        root[l][now-1]=i;
      }
    for (int i=now+1;i<=r;++i)
      if (rchnow+1,r))){
        rch=t;
        root[now+1][r]=i;
      }
    if (!(l<=now-1)) lch=1; if (!(now+1<=r)) rch=1;
    f[now][l][r]=lch*rch+score[now];
    return f[now][l][r];
}
inline void print(int l,int r){
    int now=ansroot[l][r];
    printf("%d ",now);
    if (l<=now-1) print(l,now-1);
    if (now+1<=r) print(now+1,r);
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%I64d",&score[i]);
    memset(f,-1,sizeof(f));
    for (int i=1;i<=n;++i){
        LL t=dfs(i,1,n);
        if (t>ans){
            ans=t; root[1][n]=i;
            for (int j=1;j<=n;++j)
              for (int k=j;k<=n;++k)
                ansroot[j][k]=root[j][k];
        }
    }
    printf("%I64d
",ans);
    print(1,n);
}