日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內最全IT社區平臺 聯系我們 | 收藏本站
阿里云優惠2
您當前位置:首頁 > php開源 > 綜合技術 > hdu 1561 The more, The Better 樹狀DP

hdu 1561 The more, The Better 樹狀DP

來源:程序員人生   發布時間:2015-05-11 08:59:25 閱讀次數:3281次

The more, The Better

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5844    Accepted Submission(s): 3476


Problem Description
ACboy很喜歡玩1種戰略游戲,在1個地圖上,有N座城堡,每座城堡都有1定的寶物,在每次游戲中ACboy允許攻克M個城堡并取得里面的寶物。但由于地理位置緣由,有些城堡不能直接攻克,要攻克這些城堡必須先攻克其他某1個特定的城堡。你能幫ACboy算出要取得盡可能多的寶物應當攻克哪M個城堡嗎?
 

Input
每一個測試實例首先包括2個整數,N,M.(1 <= M <= N <= 200);在接下來的N行里,每行包括2個整數,a,b. 在第 i 行,a 代表要攻克第 i 個城堡必須先攻克第 a 個城堡,如果 a = 0 則代表可以直接攻克第 i 個城堡。b 代表第 i 個城堡的寶物數量, b >= 0。當N = 0, M = 0輸入結束。
 

Output
對每一個測試實例,輸出1個整數,代表ACboy攻克M個城堡所取得的最多寶物的數量。
 

Sample Input
3 2 0 1 0 2 0 3 7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2 0 0
 

Sample Output
5 13
 

Author
8600
 

Source
HDU 2006⑴2 Programming Contest
 


鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1561


做法:設1個0節點,本身價值是0,dp[i][j]表示第i個節點,取了j個節點后的價值。由于先取父親才能取兒子,所以要從dp[i][1] 開始轉移。把子節點的狀態轉移到父親節點。

由于和分組背包1樣,子節點不能重復更新父親節點,所之外層循環父節點狀態,從大到小,內層循環子節點狀態。


#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #include <malloc.h> #include <ctype.h> #include <math.h> #include <string> #include <iostream> #include <algorithm> using namespace std; #include <stack> #include <queue> #include <vector> #include <deque> #include <set> #include <map> #define INF 999999999 #define eps 0.00001 #define LL __int64d #define pi acos(⑴.0) vector<int> son[210]; int dp[210][210]; int val[210]; int n,m; void dfs(int nw) { //dp[nw][0]=0; dp[nw][1]=val[nw]; for(int i=0;i<son[nw].size();i++) { dfs(son[nw][i]); int ss=son[nw][i]; for(int k=m;k>=1;k--) { if(dp[nw][k]!=⑴) { for(int j=1;j<=m;j++) { if(dp[ss][j]==⑴) break; dp[nw][j+k]=max(dp[ss][j]+dp[nw][k],dp[nw][j+k]); } } } } } int main() { while(scanf("%d%d",&n,&m),n||m) { memset(dp,⑴,sizeof dp); for(int i=0;i<=n;i++) { son[i].clear(); } val[0]=0; for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&val[i]); son[a].push_back(i); } dfs(0); printf("%d ",dp[0][m+1]); } return 0; }








生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關閉
程序員人生
主站蜘蛛池模板: 欧美日韩另类在线 | 中文字幕+乱码+中文字 | 黄色片看 | 日韩精品视频在线免费观看 | 国产在线精品一区二区三区 | 成人精品一区二区三区 | 久久国产精品久久 | 久久久久久久久久国产 | 美国成人毛片 | 性欧美高清come | 夜夜精品视频一区二区 | 欧美性一区二区三区 | 日本久久久一区二区三区 | 亚洲一区二区在线看 | 狠狠干导航 | 日韩精品久久久久久 | 精品乱码 | 日韩精品成人免费观看视频 | av久久久 | 欧美乱淫| 九九热在线免费视频 | 国产精品视频一区二区三区, | 欧美多人在线 | 亚洲一区二区久久久 | 操操碰| 国产高清一区 | 日日视频 | 自拍偷拍视频网站 | 国产视频一区二区在线 | 黄色毛片免费观看 | 国产区在线看 | 男女互操网站 | 免费在线观看黄色网 | 91亚洲国产成人久久精品网站 | 亚洲欧洲精品成人久久曰影片 | 亚洲欧美视频二区 | 国产午夜av| 亚洲国产成人精品久久久国产成人 | 国产在线视频一区二区 | 精品99在线观看 | 国产亚洲欧美另类一区二区三区 |