PAT 1090. 供应链最高价格-记忆化搜索+树形DP
原题链接
简单
作者:
YAX_AC
,
2024-11-15 21:08:57
,
所有人可见
,
阅读 2
//Then the next line contains N numbers, each number Si is the index of the supplier for the i-th member.
//然后下一行包含N个数字,每个数字Si是第i个成员的供应商索引。
//Sroot for the root supplier is defined to be −1.
//根供应商的Sroot定义为-1。
//you are supposed to tell the highest price we can expect from some retailers.
//你应该告诉我们一些零售商能提供的最高价格。
//expect预料,预计,期待 supposed to应该
//求叶节点到根节点的最大距离(算其产生的最高销售价格),即有多少个叶节点可以取到最短距离
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 100010;
int n;
double P,R;
int p[N],f[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;
for(int i = 0; i<n; i++) cin>>p[i];
memset(f,-1,sizeof f);
//memset(p,-1,sizeof p); 父节点不需要初始化来判断是否具有头结点,题目中已经给出根部供应商的 Sroot 为 -1
int res = 0,cnt = 0;//cnt可达到最高销售价格的零售商的数量
for(int i = 0; i<n; 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);
}