P1040-加分二叉樹
這道題放在深度優先搜索的訓練題中，可是我實在沒有看出來應該怎么搜索。看了題解以后才看出來是一個很簡單的dp(我果然還是太菜了)
看出dp并且算出來最大的分數不是很復雜，關鍵是輸出給定中序遍歷序列的二叉樹的先序遍歷，要用一個數組保存在dp的時候確定的根節點，覺得不是很容易想到。
AC代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;typedef long long ll;
const int MAXN=35;
int n,first=1;
int father[MAXN][MAXN];
ll score[MAXN][MAXN];ll search(int l,int r)
{ll tmp;if(l>r) return 1;	//如果l>r說明沒有子樹，應該為1，乘起來以后就變成了只有左子樹或者右子樹//不用考慮葉子節點，因為葉子節點的分數是它本身，所以不會進行dpif(score[l][r]==-1){for(int k=l;k<=r;k++){tmp=search(l,k-1)*search(k+1,r)+score[k][k];if(tmp>score[l][r]){score[l][r]=tmp;father[l][r]=k;	//保存這一段的根節點}}}return score[l][r];
}
void print(int l,int r)
{if(l>r) return;if(first)first=0;elseprintf(" ");printf("%d",father[l][r]);print(l,father[l][r]-1);print(father[l][r]+1,r);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&score[i][i]);father[i][i]=i;for(int j=i+1;j<=n;j++){score[i][j]=-1;}}printf("%lld\n",search(1,n));print(1,n);return 0;
}