卑微的我又在用例題刷流量，嗚
它竟然說找不到max識別符號？？，我就寫上了……
這個樹形DP不太好想，首先得定義狀態，就像數學解題設x,y一樣
一個點遍歷的最大花費深度需要從上和下兩個方向尋找所以要找到它的子節點的最大花費和父節點中不經過它的最大花費
子節點好求，在代碼dfs1()函式，父節點的話判斷是不是最大花費進過這個結點，如果是還需要次大花費
狀態轉移方程便是max(price(下),price(上))；然后price(上)=max(price(上上),price(上下（不經過此節點）));
順序需要好好考慮，先遍歷做出向下最大花費，然后通過dfs從上往下做出向上最大花費
切記臨界條件（根節點）和初始化
接下來是代碼：
#include <iostream>
#include <vector>
using namespace std;
int dp[10001][3];
int n;
struct node{
int son,cost;
node(int a,int b):son(a),cost(b){}
};
int max(int a,int b){
return (a>b)?a:b;}
vector<node>tree[10001];
void read(){
for(int i=1;i<=n;i++){
tree[i].clear();
dp[i][0]=dp[i][1]=dp[i][2]=0;
}
int s,price;
for(int i=2;i<=n;i++){
cin >> s >> price;
tree[s].push_back(node(i,price));
}
}
int dfs1(int father){
int one=0,two=0;
for(int i=0;i<tree[father].size();i++){
int price=dfs1(tree[father][i].son)+tree[father][i].cost;
if(price>one){
two=one;
one=price;
}
else if(price<=one&&price>two){
two=price;
}
}
dp[father][0]=one;
dp[father][1]=two;
return one;
}
void dfs2(int fa){
for(int i=0;i<tree[fa].size();i++){
node child=tree[fa][i];
if(dp[child.son][0]+child.cost==dp[fa][0]){
dp[child.son][2]=max(dp[fa][1],dp[fa][2])+child.cost;
}
else{
dp[child.son][2]=max(dp[fa][0],dp[fa][2])+child.cost;
}
dfs2(child.son);
}
}
int main()
{
while(cin >> n){
read();
dfs1(1);
dp[1][2]=0;
dfs2(1);
for(int i=1;i<=n;i++){
cout << max(dp[i][0],dp[i][2]) << endl;
}
}
return 0;
}
max找不到識別符號？為什么，憑什么
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/61723.html
標籤：C++
上一篇：IntelliJ IDEA快速封裝方法快捷鍵有嗎?求
下一篇：NEON的vsub方法溢位