樹形dp是建立的樹的基礎上的有二叉和三叉等等樹，現在學到的知識很簡單的樹形dp，但還是要注意深搜時要標記避免已經搜素得到過的結果可以直接用了不用在浪費時間去搜素了。還有就是對根節點的處理。

點擊打開鏈接

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> using namespace std; int dp[1005],flag[1005],cost[1005]; vector <int> g[1010]; void dfs(int x) {int k;flag[x]=1; //已經搜過了，并且會不斷搜，然后搜到結果if(g[x].size()==0){dp[x]=cost[x];return ;}for(int i =0; i<g[x].size();i++){k=g[x][i];if(flag[k]==0) //還沒有搜索過結果dfs(k);dp[x]=max(dp[x],cost[x]+dp[k]);} } int main() {int n,m;while(~scanf("%d",&n)){cost[0]=0;for(int i =1; i<=n;i++){scanf("%d",&cost[i]);g[i].clear();flag[i]=1; //注意memset只能初始化為0，-1，so}scanf("%d",&m);while(m--){int x, y;scanf("%d%d",&x,&y);g[x].push_back(y);flag[y]=0;}for(int i = 0;i < n; i++){if(flag[i])g[0].push_back(i); //存著根節點。這題存的是所有軟件包的值，所以要把所有的跟節點的中國的最大值。}memset(flag ,0,sizeof(flag));memset(dp,-1,sizeof(dp));dfs(0); //從跟節點往下搜素出答案。printf("%d\n",dp[0]);}return 0; }

總結

以上是生活随笔為你收集整理的简单的树形dp NOJ376 小强的Linux的全部內容，希望文章能夠幫你解決所遇到的問題。

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