【文件属性】:
文件名称:参考代码-动态规划-树型DP经典课件
文件大小:4.26MB
文件格式:PPT
更新时间:2021-04-25 05:25:07
动态规划
参考代码:
void DP(int a)
{ S.push(a);
memcpy(head2,head,sizeof(head));
while (!S.empty()) {
int a=S.top();
used[a]=true;
if (head2[a]){ //还有儿子没走
int tal=f[head2[a]].go;
if (!used[tal]) S.push(tal); //儿子未被访问过
head2[a]=f[head2[a]].next;
continue;
}
//儿子节点已处理完
ans[a][1]+=val[a];
ans[fa[a]][0]=max(ans[fa[a]][0],max(ans[a][0],ans[a][1])); //更新父节点
ans[fa[a]][1]=max(ans[fa[a]][1],ans[a][0]);
S.pop();//弹出该点
}
}