PAT甲级1106 Lowest Price in Supply Chain：[C++题解]树、结点到根结点的距离、树形dp、记忆化搜索

本文主要是介绍PAT甲级1106 Lowest Price in Supply Chain：[C++题解]树、结点到根结点的距离、树形dp、记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目分析

来源：acwing
分析：这道题是第三次做了。
和PAT甲级1079 Total Sales of Supply Chain：[C++题解] 树、结点到根结点的距离、树形dp、记忆化搜索是同一题，题解思路请移步。

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N =1e5 +10;
int p[N],f[N];
int n;
double P,R;
bool st[N];int dfs(int u){if(p[u] == -1) return f[u] =0;if(f[u] != -1) return f[u];return f[u] = dfs(p[u]) +1;
}
int main(){cin >> n >> P >> R;memset(f,-1,sizeof f);memset(p, -1, sizeof p);for(int i = 0; i< n; i++){int k;cin >> k;for(int j = 0; j<k; j++){int x;cin >> x;p[x] = i;}if(!k) st[i] =true;}int res = 1e9, cnt = 0;for(int i = 0; i<n; i++){if(st[i]){if(dfs(i) <res){res = dfs(i);cnt =1;}else if( dfs(i) == res) cnt++;}}printf("%.4lf %d\n",P*pow(1+R/100 ,res), cnt);
}

题目链接

PAT甲级1106 Lowest Price in Supply Chain
https://www.acwing.com/problem/content/1598/

这篇关于PAT甲级1106 Lowest Price in Supply Chain：[C++题解]树、结点到根结点的距离、树形dp、记忆化搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---