题目链接:P1040 加分二叉树
这是我自己独立完成的第一道树形(dp),(qwq)我太弱了。
其实我并没有用到什么厉害的树上算法(因为我不会),所以考虑把树上问题转化为数列的问题,可以模拟,记录下中断点(也就是树根),然后后面弄成最小字典序的情况(dfs)就行了,有一些玄学问题,虽然不知道为啥,但可以巧妙避免。
为什么这么考虑呢?
我也不知道,你看啊,对于每个子树,可以发现编号是连续的,那我们设(f[i][j])为编号从(i)到(j)构成子树的最大加分,然后我们从(2)到(n)枚举区间长度(l),得到的状态转移方程就是:
[f[i][i+l-1]=max(f[i][i+l-1],f[i][j-1]×f[j+1][i-l+1]+f[j][j]
]
(以为自己很(nb),然后发现这是大众方法。)
这里的(j)是编号(i)到(i+l-1)构成子树的根,(f[j][j])就是根的分数。
注意这里(j+1)可能大于(i-l+1),要处理一下,不要让他是(0)。
这样的复杂度是(O(n^3))的,可以通过本题,不过(n)为什么上界只有(30)呢?
(Code):
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll f[35][35];
int n,mid[35][35],vis[35];
void dfs(int l,int r)
{
if(min(l,r)<1||max(l,r)>n) return;
if(l>=r)
{
if(!vis[l]) printf("%d ",l);
vis[l]=1;
return;
}
if(!vis[mid[l][r]]) printf("%d ",mid[l][r]);
vis[mid[l][r]]=1;
dfs(l,mid[l][r]-1);
dfs(mid[l][r]+1,r);
}
void init(){for(int i=1;i<=n+1;i++)for(int j=1;j<=n;j++)if(i!=j) f[i][j]=1;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%lld",&f[i][i]);
init();
for(int l=2;l<=n;l++)
{
for(int i=1;i<=n-l+1;i++)
{
for(int j=i+1;j<=i+l-1;j++)
{
if(f[i][j-1]*f[j+1][i+l-1]+f[j][j]>f[i][i+l-1]) f[i][i+l-1]=f[i][j-1]*f[j+1][i+l-1]+f[j][j],mid[i][i+l-1]=j;
}
}
}
printf("%lld
",f[1][n]);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++) if(mid[i][j]==j) mid[i][j]=i;
}
dfs(1,n);
printf("
");
return 0;
}