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; }

總結

以上是生活随笔為你收集整理的洛谷P1040-加分二叉树-dp+二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。