PAT 1106. 供应链最低价格--记忆化搜索+树形DP
原题链接
简单
作者:
YAX_AC
,
2024-11-15 21:29:14
,
所有人可见
,
阅读 2
//求叶节点到根节点的最短距离(算其产生的最低销售价格),即有多少个叶节点可以取到最短距离
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 100010;
int n;
double P,R;
int p[N],f[N];
bool is_leaf[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);//初始化一开始都没有父节点
for(int i = 0; i<n; i++)
{
int k;
cin>>k;
for(int j = 0; j<k; j++)
{
int son;
cin>>son;
p[son] = i;
}
if(k==0) is_leaf[i] = true;//说明没有叶节点
}
memset(f,-1,sizeof f);
int res = N,cnt = 0;
for(int i = 0; i<n; i++)
if(is_leaf[i])
{
if(res > dfs(i)) res = dfs(i),cnt = 1;
else if(res == dfs(i)) cnt++;
}
printf("%.4lf %d\n",P*pow(1+R/100,res),cnt);
return 0;
}
加油!(ㅅ˙ ˘ ˙ )♡~你最棒啦!ε (๑> ₃ <) з