PAT甲级1090 Highest Price in Supply Chain：[C++题解]树、结点到根结点的距离、记忆化搜索、树形dp

本文主要是介绍PAT甲级1090 Highest Price in Supply Chain：[C++题解]树、结点到根结点的距离、记忆化搜索、树形dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目分析

来源：acwing

和PAT甲级1079 Total Sales of Supply Chain：[C++题解] 树、结点到根结点的距离、树形dp、记忆化搜索是同一题，题解思路请移步。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;int n;
double P,R; //根结点的价格，和溢价
int p[N]; //父亲数组
int f[N]; // 到根结点的距离
bool st[N]; //该点是否存在//记忆化搜索，求每点到根结点的距离
int dfs(int u){if(f[u] != -1) return f[u];if(p[u] == -1) return f[u] =0;return f[u] = dfs(p[u]) +1;
}int main(){cin >> n >> P >> R;memset(p, -1, sizeof p);memset(f, -1 ,sizeof f);for(int i = 0; i<n; i++){int father;cin >> father;p[i] =father;st[father] =true;} //res存的是最大的距离， cnt存的是个数int res = -1,cnt = 0;for(int i = 0;i<n; i++){if(!st[i]){if(dfs(i)>res){res = dfs(i);cnt =1;}else if(dfs(i) == res){cnt ++;}}}printf("%.2lf %d\n",P*pow((1+R/100),res), cnt);}

下面测试点3错误，是没有考虑到只有1个点的情况，

题目链接

PAT甲级1090 Highest Price in Supply Chain
https://www.acwing.com/problem/content/1582/

这篇关于PAT甲级1090 Highest Price in Supply Chain：[C++题解]树、结点到根结点的距离、记忆化搜索、树形dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---