PAT甲级1079 Total Sales of Supply Chain：[C++题解] 树、结点到根结点的距离、树形dp、记忆化搜索

文章目录

• • 题目分析
  • 题目链接

题目分析

来源：acwing

分析：下图是对样例的模拟图示，题目就是统计叶子结点卖出去的钱数。根据下图，我们第一步是建树，第二步是统计叶子结点到根结点的距离，然后才能知道每个叶子结点的销售价：$叶子结点售价=P\ast (1+r\%{)}^{根结点距离}$

所以：下求结点到根结点距离，然后计算即可。
令：$f[i]$表示结点i到根结点的距离。
简单的树形dp写法，用记忆化搜索的方法来求。

dfs(int u) // 返回u到根结点的距离 {if(f[u]已存在) 直接返回；if （u是根结点） 返回 f[u] = 0;//否则的话，返回父节点距离+1return dfs(p[u])+1; }

这种写法只需要存每个点的父节点，用数组p[N]表示。

记忆化搜索，时间复杂度O(n)

ac代码

#include<bits/stdc++.h> using namespace std;const int N = 1e6+10; int n; double P,R; //P售卖价格，R是溢价百分比 int p[N]; //父亲数组 int f[N];//到根结点的距离 int cnt[N]; //叶结点卖出去的数量//返回结点u到根结点的距离 //记忆化搜索，f[n]数组会存到根结点的距离 int dfs(int u){//if( f[u] != -1) return f[u];//根结点返回0if( p[u] == -1) return f[u] =0;//return f[u] = dfs(p[u]) +1; } int main(){//父亲数组初始化为-1，表示都没有父节点memset(p ,-1, sizeof p);cin >> n >> P >> R;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; // 记录 son结点的父节点是i}//如果k==0，是叶子结点，统计该结点售卖的件数if(!k) cin>> cnt[i];}//到根结点距离初始化为-1，表示不可达memset(f,-1,sizeof f);double res = 0;for(int i = 0; i < n; i++){if(cnt[i]) res += cnt[i] *P * pow(1+R/100,dfs(i));}printf("%.1lf\n",res); }

题目链接

PAT甲级1079 Total Sales of Supply Chain
https://www.acwing.com/problem/content/1567/

总结

以上是生活随笔为你收集整理的PAT甲级1079 Total Sales of Supply Chain：[C++题解] 树、结点到根结点的距离、树形dp、记忆化搜索的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。