HDU 1561 The more, The Better - 가방 의존 + 트 리 dp 기반
/*
http://acm.hdu.edu.cn/showproblem.php?pid=1561 The more, The Better
-> dp
: , max , , 。
:
dp[i][j] : i j dp[i][j];
:i dp[i][2,3,4,5...] -1( , )
1. P , P (1) , (2) ;
2. P ,
dp[P'father][i] = max(dp[P'father][i], dp[P'father][j]+dp[P][k]) (j + k = i ,j>0,k>0,2<=i<=max_cost, i (j,k) )
dp[P'father][j] j P j
root (dp[0][i])
3. dp[0][max_cost]
max_cost
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
[i]:v i v; [0]root [0]:0
[0]root
/ \
[2]:1 [3]:4
/ | \
[1]:2 [4]:1 [7]:2
/ \
[5]:1 [6]:6
*/
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define CLR(c,v) memset(c,v,sizeof(c))
template <typename _T>
_T Max(_T a, _T b){
return (a>b)?(a):(b);
}
template <typename _T>
_T Max(_T a, _T b,_T c){
return (a>Max(b,c))?(a):(Max(b,c));
}
template <typename _T>
_T Min(_T a, _T b){
return (a<b)?(a):(b);
}
template <typename _T>
_T Min(_T a, _T b,_T c){
return (a<Min(b,c))?(a):(Min(b,c));
}
const int inf = -(1<<30);
const int INF = (1<<30);
const int M = 2e2 + 10;
vector <int > list[M];
int dp[M][M];
int n,max_cost;
void dfs(int father){
for (int i = 0 ; i < list[father].size() ; i++){
int child = list[father][i]; //
if(list[child].size() > 0)
dfs(child);
for(int j = max_cost ; j > 1 ; j--){// , j ,j>1
for(int k = 1 ; k < j ; k++ ){ // k + j-k == j
dp[father][j] = Max(dp[father][j] ,dp[father][k] + dp[child][j-k]);
}
}
}
}
int main(){
freopen("in.txt", "r", stdin);
while(cin >> n >> max_cost , n&&max_cost){
max_cost ++; // , root , 。
CLR(dp,0);
for(int i = 1 ; i <= n ; i ++){
int a , b;
cin >> a >> b;
list[a].push_back(i);
for(int j = 1 ; j <= max_cost ; j++)
dp[i][j] = b; // , ,
}
dfs(0);
for(int i = 0 ; i <= n ; i ++)
list[i].clear();
cout << dp[0][max_cost] << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.