<span>hihocoder1199 Tower Defense Game(树形dp)</span>
题意:
给定一颗以1
为根节点的树,每个节点有一个购入价格p
和卖出价格q
。
进入一个节点时需要花费p
,离开时可以收回q
,每个节点只产生一次购入和卖出。
请你选择一个遍历的顺序,要求在遍历的过程中身上的钱数不小于0,且出发时带的钱数最少。
按照遍历的顺序是指:当你选择了一颗子树之后,你需要将这个子树全部走完,才能选择其他子树。
思路:
该题为一道树形图上的贪心问题。
我们每一步的决策在于:当遍历到一个根时,对于其拥有的若干颗子树,应该以怎样的顺序来遍历这些子树。
先将问题简化为二叉树,并且两颗子树都只有根节点:
首先我们选择左边的路径,则需要携带的钱数为:
经过1: L1 = p1
经过2: L2 = p1-q1+p2
经过3: L3 = p1-q1+p2-q2+p3
然后考虑走右边的情况:
经过1: R1 = p1
经过3: R2 = p1-q1+p3
经过2: R3 = p1-q1+p3-q3+p2
对于这6个值,我们要求的是min( max(L1, L2, L3), max(R1, R2, R3) )
由于在题目中已经明确说明总是有p≥q
,可以肯定有L3≥R2,R3≥L2
,所以可以直接将L2
和R2
排除。
又因为1是必经之路,因此在选择左右时,实际上需要比较的只有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
的值是确定的,因此实际上我们只需要根据q2
和q3
的值就可以选择走哪边。
最后的结论也就是:对于二叉树的情况,我们选择q值大的一边先走,一定能保证结果值最小
那么接下来将这个结论推广至多叉树的情况:
对于多叉树的情况,我们将子树按照q值从大到小的顺序,一定能保证结果值最小
这是由于q值之间的大小顺序是绝对的,假设3个子节点分别为A
,B
,C
,若qA≥qB
,qB≥qC
,则一定有qA≥qC
。
不妨举个例子:
根据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
那么还有一个问题,一个节点的p
和q
是直接给定的,我们应该如何来求一颗子树的pt
和qt
(为了便于区分,我们将树的p
和q
记为pt
和qt
)?
在计算过程中,我们采用递归的从根节点开始遍历。在计算当前节点时,我们需要将其子树的p
和q
都先计算出来。
因此在计算当前子树时,我们已经知道了根节点的p
和q
,以及每颗子树的pt
和qt
(记作pt1,pt2,pt3,...
和qt1,qt2,qt3,...
,并且满足qt1≥qt2≥qt3≥...
)。
在该题中所有节点的总购买钱数不会超过200,000,000,不妨设置一个初始钱数wallet = 200000000
。
同时我们还需要一个值minWallet
,来记录钱包钱数最少时的值,初始也为200,000,000。
首先处理根节点:
wallet = wallet - p
If (minWallet > wallet) Then
minWallet = wallet
End If
wallet = wallet + q
接下来处理每个子树:
For i = 1 .. chdNumber
wallet = wallet - pt[i]
If (minWallet > wallet) Then
minWallet = wallet
End If
wallet = wallet + qt[i]
End For
最后可以得到整个树的p
和q
分别为:
pt[root] = 200000000 - minWallet // 遍历这颗树至少需要的钱数
qt[root] = wallet - minWallet // 最后的钱数-花费的钱数=返还的钱数
完整的伪代码为:
DFS(rt):
wallet = 200000000
minWallet = 200000000
// 先递归处理每个子树
For each child i of rt
DFS(i)
End For
// 对该根节点的所有子树按照qt值排序
sortByQt(children)
// 处理根节点
wallet = wallet - p[rt]
If (minWallet > wallet) Then
minWallet = wallet
End If
wallet = wallet + q[rt]
// 处理子树
For each child i of rt
wallet = wallet - pt[i]
If (minWallet > wallet) Then
minWallet = wallet
End If
wallet = wallet + qt[i]
End For
// 记录子树
pt[rt] = 200000000 - minWallet
qt[rt] = wallet - minWallet
最后所求的结果是pt[1]
。
由于在每一颗子树都使用了排序,最后这个算法的时间复杂度为O(NlogN),即使在N
为10000的数据下,也能够顺理通过。
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> #define inf 0x3f3f3f3f #define LL long long #define rep(i,a,b) for(int i=a;i<=b;i++) #define dec(i,a,b) for(int i=a;i>=b;i--) #define ou(a) printf("%d\n",a) #define pb push_back #define mkp make_pair template<class T>inline void rd(T &x){char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-'0';c=getchar();}} #define IN freopen("in.txt","r",stdin); #define OUT freopen("out.txt","w",stdout); using namespace std; const int mod=1e9+7; const int N=1e4+10; int n,p[N],q[N],pt[N],qt[N],x,y; vector<int>eg[N]; bool cmp(int a,int b) { return qt[a]>qt[b]; } void dfs(int u,int pre) { int all=inf,miall=inf; rep(i,0,eg[u].size()-1) if(eg[u][i]!=pre) dfs(eg[u][i],u); sort(eg[u].begin(),eg[u].end(),cmp); all-=p[u]; miall=min(miall,all); all+=q[u]; rep(i,0,eg[u].size()-1) { if(eg[u][i]==pre) continue; all-=pt[eg[u][i]]; miall=min(miall,all); all+=qt[eg[u][i]]; } pt[u]=inf-miall; qt[u]=all-miall; } int main() { rd(n); rep(i,1,n) rd(p[i]),rd(q[i]); rep(i,1,n-1) { rd(x),rd(y); eg[x].pb(y); eg[y].pb(x); } dfs(1,0); ou(pt[1]); return 0; }