由電視臺，中轉站，和用戶的電視組成的體系剛好是一棵樹

n個節點，編號分別為1~n，1是電視臺中心，2~n-m是中轉站，n-m+1~n是用戶，1為root

現在節點1準備轉播一場比賽，已知從一個節點傳送數據到達另一個節點，電視臺需要一定的費用

若可以傳送數據到達用戶的節點n-m+1~n，這些用戶各自愿意支付一定的費用給電視臺

現在電視臺希望在不虧本的情況下為盡量多的用戶轉播比賽

?

輸出最多可以為多少用戶轉播比賽

?

背包類型的樹形DP第一題

?

dp[i][j]表示以節點i為根的子樹有j個用戶獲得轉播，電視臺的最大收益

由于收益有正有負

初始化：

dp[i][0]=0

dp[i][j]=-inf(j>0)

目標：dp[1][j]>=0的條件下最大的j

(dp[1][j]>=0表示電視臺不虧本)

?

dfs的過程遞推dp

?

有個主意的地方寫在了注釋

?

1 #include<cstdio> 2 #include<cstring> 3 4 using namespace std; 5 6 inline int max(int a,int b) 7 { 8 return a>b?a:b; 9 } 10 11 const int maxn=3005; 12 const int inf=0x3f3f3f3f; 13 14 int dp[maxn][maxn]; 15 int cost[maxn][maxn]; 16 int siz[maxn]; 17 struct Edge 18 { 19 int to,next; 20 }; 21 Edge edge[maxn]; 22 int head[maxn]; 23 int tot; 24 int n,m; 25 26 void addedge(int u,int v) 27 { 28 edge[tot].to=v; 29 edge[tot].next=head[u]; 30 head[u]=tot++; 31 } 32 33 void init() 34 { 35 memset(head,-1,sizeof head); 36 tot=0; 37 for(int i=1;i<=n;i++) 38 { 39 dp[i][0]=0; 40 for(int j=1;j<=m;j++) 41 dp[i][j]=-inf; 42 } 43 } 44 45 void solve(); 46 void dfs(int u); 47 48 int main() 49 { 50 while(~scanf("%d",&n)) 51 { 52 scanf("%d",&m); 53 init(); 54 for(int i=1;i<=n-m;i++) 55 { 56 int num; 57 scanf("%d",&num); 58 while(num--) 59 { 60 int u; 61 scanf("%d",&u); 62 scanf("%d",&cost[i][u]); 63 addedge(i,u); 64 } 65 } 66 for(int i=n-m+1;i<=n;i++) 67 { 68 scanf("%d",&cost[i][maxn-1]); 69 } 70 solve(); 71 } 72 return 0; 73 } 74 75 void solve() 76 { 77 dfs(1); 78 for(int j=siz[1];j>=0;j--) 79 { 80 if(dp[1][j]>=0) 81 { 82 printf("%d\n",j); 83 return ; 84 } 85 } 86 /* 87 for(int i=0;i<=siz[1];i++) 88 printf("%d\n",dp[1][i]); 89 */ 90 } 91 92 void dfs(int u) 93 { 94 siz[u]=0; 95 for(int i=head[u];~i;i=edge[i].next) 96 { 97 int v=edge[i].to; 98 if(n-m<v) 99 { 100 dp[v][0]=0; 101 dp[v][1]=cost[v][maxn-1]; 102 siz[v]=1; 103 } 104 else 105 { 106 dfs(v); 107 } 108 siz[u]+=siz[v]; 109 110 //由于更新dp[u][j]的時候 111 //dp[u][j-k]需要表示以u為根的子樹，有j-k個是從前面的兒子節點取的 112 //所以這個時候dp[u][j-k]不可以被兒子節點v更新過（保證j-k個都是從前面取的） 113 //所以遞推時j要逆推 114 //當然，k和j循環的順序也就不可以交換了 115 for(int j=siz[u];j>0;j--) 116 { 117 for(int k=1;k<=siz[v];k++) 118 if(j>=k) 119 dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]-cost[u][v]); 120 } 121 } 122 } View Code

?

轉載于:https://www.cnblogs.com/-maybe/p/4749155.html

總結

以上是生活随笔為你收集整理的POJ 1155 TELE 背包型树形DP 经典题的全部內容，希望文章能夠幫你解決所遇到的問題。

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