[PAT解题报告] Highest Price in Supply Chain
和1079很像，简单地说就是根节点有个价格，孩子节点总是在父亲节点的价格上加一个比例，求最贵的节点——显然是个叶子。
题目输入给了每个节点i的父亲f[i]， 除了根节点外，那么i的价格实际上就是a[f[i]] * r
(r是一个大于1的数），因此我们只要dfs计算就可以了，当然已经计算过的结果不要重复计算，我用了-1.e6表示负无穷，然后get一下每个节点的价格选出最大的就可以了。简单题。
代码：
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const double eps = 1.e-8;
int f[100005];
double a[100005];
double r;
double get(int x) {
if (a[x] > -1.) {
return a[x];
}
return a[x] = get(f[x]) * r;
}
int main() {
int n;
double p;
scanf("%d%lf%lf",&n,&p,&r);
r /= 100.;
r += 1.;
for (int i = 0; i < n; ++i) {
scanf("%d",f + i);
a[i] = (f[i] < 0)?p:(-1.e6);
}
double answer = -1.e6;
int num;
for (int i = 0; i < n; ++i) {
double may = get(i);
if (may >= answer + eps) {
answer = may;
num = 1;
}
else if ((may + eps > answer) && (may < answer + eps)) {
++num;
}
}
printf("%.2lf %d\n", answer, num);
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1090
查看25道真题和解析