computer

卑微的我又在用例题刷流量，呜

 

它竟然说找不到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.cnblogs.com/sos3210/p/12313352.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有