BT based DP for max score
之前只做过一道基于BT的DP，还是瞿神一起讨论的，大学四年真的是代码写的太少。。。。
之前一道是计算BT里的最大pathsum, 任意起点终点，类似于记忆话存储，由于自己BT总是陷入指针，因此代码写的很繁琐，又是后续遍历推进，
又是层序遍历计算index，其实很多都可以缩减。
这道也是一样，https://vijos.org/p/1100
初看以为两边子树互相影响，然后不是DP，但是后来adhoc提示到左右子树都是连续的，因此可以DP，暂时不需要考虑树的样子。
DP方程 F(i,j)=max (F(i,k-1)*F(k+1,j)+A[k]) , i+1<=k<=j-1
只要重叠子问题首选DP，正如瞿神所说。后面再类似矩阵连s[i][j]记录断链位置，此处是根的位置，然后用递归构造先序遍历
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
LL dp[30+1][30+1];
int s[30+1][30+1];
LL A[30+1];
vector<int> PreVec;
int n;
LL btmaxscore()
{
//int length;
for(int i=1;i<=n;i++)
dp[i][i]=A[i],s[i][i]=i;
//for(int i=1;i<=n-1;i++)
// dp[i][i+1]=1;
for(LL length=2;length<=n;length++)
{
for(LL i=1;i<=n;i++)
{
LL j=i+length-1,max;
max=1*dp[i+1][j]+A[i];s[i][j]=i;
if(max<dp[i][j-1]*1+A[j])
max=dp[i][j-1]*1+A[j],s[i][j]=j;
for(LL k=i+1;k<=j-1;k++)
{
if(max<dp[i][k-1]*dp[k+1][j]+A[k])
max=dp[i][k-1]*dp[k+1][j]+A[k],s[i][j]=k;
}
dp[i][j]=max;
}
}
/*
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}*/
return dp[1][n];
}
void PreOrder(int i, int j)
{
if(i<=j)
{
PreVec.push_back(s[i][j]);
PreOrder(i,s[i][j]-1);
PreOrder(s[i][j]+1,j);
}
}
int main()
{
//freopen("in.txt","r",stdin);
//int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%I64d",&A[i]);
LL maxscore=btmaxscore();
PreVec.clear();
PreOrder(1,n);
printf("%I64d\n%d",maxscore,PreVec[0]);
for(int i=1;i<PreVec.size();i++)
printf(" %d",PreVec[i]);
printf("\n");
}
return 0;
}