树型DP入门题

题目链接：http://acm.sjtu.edu.cn/OnlineJudge/problem/1077

•设f(i,j)中序遍历为i,i+1,…,j的二叉树的最大加分，则有：

  f(i,j)=max{f[i,k-1]*f[k+1,j] +d[k]}

•显然 f(i,i)=d[i]

•答案为f(1,n)

•1<=i<=k=<=j<=n

•时间复杂度  O(n3)

•要构造这个树，只需记录每次的决策值，令b(i,j)=k，表示中序遍历为i,i+1,…,j的二叉树的取最优决策时的根结点为k

最后前序遍历这个树即可。

 

/*树型DP*/#include 
     
      #include 
      
       #include 
       
        using namespace std;#define MAX 35#define INF 0x3f3f3f3flong long dp[MAX][MAX];int p[MAX][MAX];int a[MAX];queue
        
         q;long long dfs(int i ,int j){  if(i>j) return dp[i][j]=1;  if(dp[i][j]!=-1) return dp[i][j];  dp[i][j]=-INF;  for(int k=i; k<=j; k++)  {    long long t1=dfs(i,k-1);    long long t2=dfs(k+1,j);    if(t1*t2+a[k] > dp[i][j])    {      dp[i][j]=t1*t2+a[k];      p[i][j]=k;    }  }  return dp[i][j];}void travel(int i ,int j){  if(i>j) return ;  if(i==j)  {    q.push(i);    return ;  }  int k=p[i][j];  q.push(k);  travel(i,k-1);  travel(k+1,j);}int main(){  int n;  while(scanf("%d",&n)!=EOF)  {    for(int i=1; i<=n; i++) scanf("%d",&a[i]);    memset(p,-1,sizeof(p));    memset(dp,-1,sizeof(dp));    for(int i=1; i<=n; i++)    {      dp[i][i]=a[i];      p[i][i]=i;    }    dfs(1,n);    printf("%lld\n",dp[1][n]);    while(!q.empty()) q.pop();    travel(1,n);    printf("%d",q.front());    q.pop();    while(!q.empty())    {      printf(" %d",q.front());      q.pop();    }    printf("\n");  }  return 0;}