文章目錄

• • 題目分析
  • 題目鏈接

題目分析

來源：acwing

分析：下圖是對樣例的模擬圖示，題目就是統(tǒng)計葉子結點賣出去的錢數(shù)。根據(jù)下圖，我們第一步是建樹，第二步是統(tǒng)計葉子結點到根結點的距離，然后才能知道每個葉子結點的銷售價：$葉子結點售價=P?(1+r\%{)}^{根結點距離}$

所以：下求結點到根結點距離，然后計算即可。
令：$f[i]$表示結點i到根結點的距離。
簡單的樹形dp寫法，用記憶化搜索的方法來求。

dfs(int u) // 返回u到根結點的距離 {if(f[u]已存在) 直接返回；if （u是根結點） 返回 f[u] = 0;//否則的話，返回父節(jié)點距離+1return dfs(p[u])+1; }

這種寫法只需要存每個點的父節(jié)點，用數(shù)組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]; //父親數(shù)組 int f[N];//到根結點的距離 int cnt[N]; //葉結點賣出去的數(shù)量//返回結點u到根結點的距離 //記憶化搜索，f[n]數(shù)組會存到根結點的距離 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(){//父親數(shù)組初始化為-1，表示都沒有父節(jié)點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結點的父節(jié)點是i}//如果k==0，是葉子結點，統(tǒng)計該結點售賣的件數(shù)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、记忆化搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。