PAT(Advanced Level)A1090. Highest Price in Supply Chain

题意

供应链有3种人，零售商，经销商和供应商，供应链上的人都可以从自己的供应商那里以P的价格买入，而后以r%的涨幅卖出去，求最深的结点的售价是多少

思路

• DFS找到最深的即可
  • 1⃣️没有下一级的结点就是DFS递归退出的边界
  • 不同层的销售价格可以通过pow(1 + r，层数)方便地进行计算，而我们递归的参数之一depth的含义就是当前为第几层
• ⚠️
  • 题目给出的r是已经去掉%号的，所以要/100

代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
int members, root;
struct node{
    vector<int> child;      //表示所有下一级的
};
double init_price, increment, ans = -1.0;   //对应其实价格，增量，和解
int sum = 0;    //统计个数
vector<node> v;
void dfs(int cur, int depth)
{
    if(v[cur].child.size() == 0)    //到达递归边界，进行计算
    {
        double path = init_price * pow(1 + increment, depth);
        if(path > ans)
        {
            ans = path;
            sum = 1;
        }else if(path == ans){
            sum++;
        }
    }
    for(int i=0;i<v[cur].child.size();i++)      //遍历当前结点cur的所有下一级
        dfs(v[cur].child[i], depth + 1);
}
int main()
{
    cin >> members >> init_price >> increment;
    increment /= 100;
    int t;
    v.resize(members);
    for(int i=0;i<members;i++)
    {
        scanf("%d", &t);
        if(t == -1)     //如果是-1，也就是root supplier，将其指向的设置为root
            root = i;
        else
            v[t].child.emplace_back(i);     //统计孩子
    }
    dfs(root, 0);
    printf("%.2f %d
", ans, sum);
    return 0;
}