1090 Highest Price in Supply Chain
A supply chain is a network of retailers（零售商）, distributors（经销商）, and suppliers（供应商）-- everyone involved in moving a product from supplier to customer.
Starting from one root supplier, everyone on the chain buys products from one’s supplier in a price P and sell or distribute them in a price that is r% higher than P. It is assumed that each member in the supply chain has exactly one supplier except the root supplier, and there is no supply cycle.
Now given a supply chain, you are supposed to tell the highest price we can expect from some retailers.
Input Specification:
Each input file contains one test case. For each case, The first line contains three positive numbers: N (≤105), the total number of the members in the supply chain (and hence they are numbered from 0 to N−1); P, the price given by the root supplier; and r, the percentage rate of price increment for each distributor or retailer. Then the next line contains N numbers, each number S**i is the index of the supplier for the i-th member. Sroot for the root supplier is defined to be −1. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the highest price we can expect from some retailers, accurate up to 2 decimal places, and the number of retailers that sell at the highest price. There must be one space between the two numbers. It is guaranteed that the price will not exceed 1010.
Sample Input:
9 1.80 1.00 1 5 4 4 -1 4 5 3 6 • 1 • 2
Sample Output:
1.85 2
题意
供应链是由零售商，经销商和供应商构成的销售网络，每个人都参与将产品从供应商转移到客户的过程。
整个销售网络可以看作一个树形结构，从根部的供应商往下，每个人从上一级供应商中买入商品后，假定买入价格为 P ，则会以高出买入价 r% 的价格向下出售。
只有零售商（即叶节点）可以直接将产品销售给顾客。
现在，给定整个销售网络，输出零售商可达到的最高销售价格，保留两位小数，以及可达到最高销售价格的零售商的数量。
第一行包含三个数，N 表示供应链总成员数（所有成员编号从 0 到 N−1 ，根部供应商编号为 0 ），P 表示根部供应商的每件产品的售卖价格，r ，溢价百分比。
接下来一行输出 N 个数，分别表示 i 的上级供应商编号。
思路
我们可以用一个数组 p 来存储每个结点的父结点，并且再用一个数组 st 来判断每个结点是否是叶子结点。另外，给定上级结点编号是 -1 的结点是根结点。
通过树形 DP 来计算树的深度，用一个 f 数组来存储每次计算的值，这样就可以排除重复计算的步骤。
计算总销售额时只用判断每次遍历的结点是否为叶子结点即可，然后通过公式 P * pow(1 + R / 100, dfs(i)) 计算该叶子结点即零售商的销售额。其中，P 表示产品的单位价格，pow(1 + R / 100, dfs(i)) 则是计算 1 + R/100 的 dfs(i) 次方即每多一层关系次方数就加 1 。每次计算完之后，再去判断当前销售额是否是最大值，如果是最大值则更新答案，如果等于最大值则最大销售额的销售商数量加 1 。
输出最终结果，注意销售额最大值保留两个小数点。
代码
#include<bits/stdc++.h> using namespace std; const int N = 100010; int n; double P, R; int p[N], f[N]; bool st[N]; //树形DP，记忆化搜索 int dfs(int u) { //剪枝，如果f[u]已经被计算过，直接返回即可 if (f[u] != -1) return f[u]; //如果该结点没有父结点，直接返回0，同时更新f[u] if (p[u] == -1) return f[u] = 0; return f[u] = dfs(p[u]) + 1; } int main() { cin >> n >> P >> R; //输入结点信息 int root = 0; for (int i = 0; i < n; i++) { cin >> p[i]; st[p[i]] = true; if (p[i] == -1) root = i; } memset(f, -1, sizeof f); //找到零售商可达到的最高销售价格及该零售商的数量 double res = 0; int cnt = 0; for (int i = 0; i < n; i++) if (!st[i]) { double sum = P * pow(1 + R / 100, dfs(i)); if (sum > res) res = sum, cnt = 1; else if (sum == res) cnt++; } printf("%.2lf %d\n", res, cnt); return 0; }
