PAT 1079. 供应链总销售额-记忆化搜索+树形DP
原题链接
简单
作者:
YAX_AC
,
2024-11-15 20:46:34
,
所有人可见
,
阅读 2
//unit price单价 distributor经销商 price increment价格上涨价格增加
// the unit price given by the root supplierand r, the percentage rate of price increment for each distributor or retailer.
//由根供应商和r给出的单价,每个分销商或零售商的价格增长百分比。
#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],cnt[N];
//p[u]:指u的父节点
//f[u]:指u到根节点的距离
//cnt[u]:u节点卖出的数量
int dfs(int u)
{
if(f[u]!=-1) return f[u];
if(p[u]==-1) return f[u] = 0;//u为根节点
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) cin>>cnt[i];
}
memset(f,-1,sizeof f);
double res = 0;
for(int i = 0; i<n; i++)
if(cnt[i])//只要计算所有销量不为0的点
res += cnt[i]*P*pow(1+R/100,dfs(i));
printf("%.1lf",res);
return 0;
}