題目大意

給定一顆以1為根節(jié)點的樹，每個節(jié)點有一個購入價格p和賣出價格q。

進入一個節(jié)點時需要花費p，離開時可以收回q，每個節(jié)點只產生一次購入和賣出。

請你選擇一個遍歷的順序，要求在遍歷的過程中身上的錢數(shù)不小于0，且出發(fā)時帶的錢數(shù)最少。

按照遍歷的順序是指：當你選擇了一顆子樹之后，你需要將這個子樹全部走完，才能選擇其他子樹。

解題思路

該題為一道樹形圖上的貪心問題。

我們每一步的決策在于：當遍歷到一個根時，對于其擁有的若干顆子樹，應該以怎樣的順序來遍歷這些子樹。

先將問題簡化為二叉樹，并且兩顆子樹都只有根節(jié)點：

首先我們選擇左邊的路徑，則需要攜帶的錢數(shù)為：

經(jīng)過1:?L1 = p1

經(jīng)過2:?L2 = p1-q1+p2

經(jīng)過3:?L3 = p1-q1+p2-q2+p3

然后考慮走右邊的情況：

經(jīng)過1:?R1 = p1

經(jīng)過3:?R2 = p1-q1+p3

經(jīng)過2:?R3 = p1-q1+p3-q3+p2

對于這6個值，我們要求的是min( max(L1, L2, L3), max(R1, R2, R3) )

由于在題目中已經(jīng)明確說明總是有p≥q，可以肯定有L3≥R2,R3≥L2，所以可以直接將L2和R2排除。

又因為1是必經(jīng)之路，因此在選擇左右時，實際上需要比較的只有L3和R3。

我們將L3和R3換一種形式表示：pSum = p1+p2+p3, qSum = q1+q2+q3，則L3=pSum-qSum+q3,R3=pSum-qSum+q2

若L3>R3，則有q3>q2，此時要選擇的是R3，即走右路；

若L3<R3，則有q2>q3，此時要選擇的是L3，即走左路。

由于pSum和qSum的值是確定的，因此實際上我們只需要根據(jù)q2和q3的值就可以選擇走哪邊。

最后的結論也就是：對于二叉樹的情況，我們選擇q值大的一邊先走，一定能保證結果值最小

那么接下來將這個結論推廣至多叉樹的情況：

對于多叉樹的情況，我們將子樹按照q值從大到小的順序，一定能保證結果值最小

這是由于q值之間的大小順序是絕對的，假設3個子節(jié)點分別為A,B,C，若qA≥qB,qB≥qC，則一定有qA≥qC。

不妨舉個例子：

根據(jù)q值，對應的6種遍歷順序分別為：

1,2,3：需要帶錢8 1,3,2：需要帶錢7 2,1,3：需要帶錢8 2,3,1：需要帶錢7 3,1,2：需要帶錢7 3,2,1：需要帶錢6

那么還有一個問題，一個節(jié)點的p和q是直接給定的，我們應該如何來求一顆子樹的pt和qt（為了便于區(qū)分，我們將樹的p和q記為pt和qt）？

在計算過程中，我們采用遞歸的從根節(jié)點開始遍歷。在計算當前節(jié)點時，我們需要將其子樹的p和q都先計算出來。

因此在計算當前子樹時，我們已經(jīng)知道了根節(jié)點的p和q，以及每顆子樹的pt和qt（記作pt1,pt2,pt3,...和qt1,qt2,qt3,...，并且滿足qt1≥qt2≥qt3≥...）。

在該題中所有節(jié)點的總購買錢數(shù)不會超過200,000,000，不妨設置一個初始錢數(shù)wallet = 200000000。

同時我們還需要一個值minWallet，來記錄錢包錢數(shù)最少時的值，初始也為200,000,000。

首先處理根節(jié)點：

wallet = wallet - p If (minWallet > wallet) ThenminWallet = wallet End If wallet = wallet + q

接下來處理每個子樹：

For i = 1 .. chdNumberwallet = wallet - pt[i]If (minWallet > wallet) ThenminWallet = walletEnd Ifwallet = wallet + qt[i] End For

最后可以得到整個樹的p和q分別為：

pt[root] = 200000000 - minWallet // 遍歷這顆樹至少需要的錢數(shù) qt[root] = wallet - minWallet // 最后的錢數(shù)-花費的錢數(shù)=返還的錢數(shù)

完整的偽代碼為：

DFS(rt):wallet = 200000000minWallet = 200000000// 先遞歸處理每個子樹For each child i of rtDFS(i)End For// 對該根節(jié)點的所有子樹按照qt值排序sortByQt(children)// 處理根節(jié)點wallet = wallet - p[rt]If (minWallet > wallet) ThenminWallet = walletEnd Ifwallet = wallet + q[rt]// 處理子樹For each child i of rtwallet = wallet - pt[i]If (minWallet > wallet) ThenminWallet = walletEnd Ifwallet = wallet + qt[i]End For// 記錄子樹pt[rt] = 200000000 - minWalletqt[rt] = wallet - minWallet

最后所求的結果是pt[1]。

由于在每一顆子樹都使用了排序，最后這個算法的時間復雜度為O(NlogN)，即使在N為10000的數(shù)據(jù)下，也能夠順理通過。

#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std;const int maxn = 10005; const int inf = 200000000; struct Node {vector<int> child; }tree[maxn]; int n,p[maxn],q[maxn]; int pt[maxn],qt[maxn];bool cmp(int a,int b) {return qt[a] > qt[b]; }void dfs(int u,int fa) {int Wallet = inf;int minWallet = inf;vector<int> V = tree[u].child;for(int i = 0; i < V.size(); i++){int v = V[i];if(v == fa) continue;dfs(v,u);}sort(V.begin(),V.end(),cmp);Wallet = Wallet - p[u];if(minWallet > Wallet)minWallet = Wallet;Wallet = Wallet + q[u];for(int i = 0; i < V.size(); i++){if(V[i] == fa) continue;Wallet = Wallet - pt[V[i]];if(minWallet > Wallet)minWallet = Wallet;Wallet = Wallet + qt[V[i]];}pt[u] = inf - minWallet;qt[u] = Wallet - minWallet; }int main() {int u,v;while(scanf("%d",&n)!=EOF){for(int i = 1; i <= n; i++)scanf("%d%d",&p[i],&q[i]);for(int i = 1; i <= n; i++) tree[i].child.clear();for(int i = 1; i < n; i++){scanf("%d%d",&u,&v);tree[u].child.push_back(v);tree[v].child.push_back(u);}dfs(1,0);printf("%d\n",pt[1]);}return 0; }

總結

以上是生活随笔為你收集整理的hihocoder Tower Defense Game(树上贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

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