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

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

文章目录

- 题目分析
- 题目链接

题目分析

在这里插入图片描述

来源：acwing

分析：下图是对样例的模拟图示，题目就是统计叶子结点卖出去的钱数。根据下图，我们第一步是建树，第二步是统计叶子结点到根结点的距离，然后才能知道每个叶子结点的销售价： $叶子结点售价= P*(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);
}