讨论 / 简单的树形动规……
wrongnumber 2016-01-29 22:51:23
点我顶贴 收藏 删除
题意似乎有点不清 当二叉树只有一个分叉的情况……隐隐觉得有字漏打了

#include<iostream>

#include<cstdio>

using namespace std;

struct data{

int i,ans;

}dp[52][52];

int n,a[52];

bool used[52][52];

int dfs(int i,int j,int le)

{

if (used[i][j]) return dp[i][j].i;

used[i][j]=true;

if (i>j) return 0;

int t;

for (int q=i+1;q<=j-1;q++)

{

t=(dfs(i,q-1,le+1)*dfs(q+1,j,le+1))+a[q];

if(t>dp[i][j].i)

{

dp[i][j].i=t;

dp[i][j].ans=q;

}

}

t=a[i]+dfs(i+1,j,le+1);

if(t>dp[i][j].i)

{

dp[i][j].i=t;

dp[i][j].ans=i;

}

t=a[j]+dfs(i,j-1,le+1);

if(t>dp[i][j].i)

{

dp[i][j].i=t;

dp[i][j].ans=j;

}

return dp[i][j].i;

}

void print(int l,int r)

{

if (l>r) return ;

printf("%d ",dp[l][r].ans+1);

print(l,dp[l][r].ans-1);

print(dp[l][r].ans+1,r);

}

int main()

{

scanf("%d",&n);

for (int q=0;q<n;q++) scanf("%d",&a[q]);

printf("%d\n",dfs(0,n-1,0));

print(0,n-1);

return 0;

}

查看更多回复
提交回复