Involving knowledge points
Deep optimization (DFS) memoization
Title
There is an undirected tree consisting of n nodes at node 0, with node numbers from 0 to n – 1. You are given a two-dimensional integer array edges of length n – 1, where edges[i] = [ai, bi] means that there is an edge between nodes ai and bi on the tree. You are also given an array coins with indexes starting from 0 and length n and an integer k, where coins[i] represents the number of gold coins at node i.
Starting from the root node, you must collect all gold coins. To collect gold coins on a node, you must first collect gold coins on the node’s ancestor nodes.
Gold coins on node i can be collected using one of the following methods:
Collect all gold coins and get a total of coins[i] – k points. If coins[i] – k is negative, you will lose abs(coins[i] – k) points.
Collect all gold coins and get a total of floor(coins[i] / 2) points. If this method is adopted, the number of gold coins coins[j] of all nodes j in the subtree of node i will be reduced to floor(coins[j] / 2).
Returns the maximum points that can be obtained after collecting gold coins from all tree nodes.
Parameter range:
n == coins.length
2 <= n <= 105
0 <= coins[i] <= 104
edges.length == n – 1
0 <= edges[i][0], edges[i][1] < n
0 <= k <= 104
Analysis
Time complexity
O (number of nodes), the number of DFS calls = number of nodes * 2 (two methods) * 21 (split method), when n is infinite, 2 and 21 are ignored.
Core principles
When there is an ancestor node in the second method, the gold coins of this node will be halved. Since there are at most 10,000 gold coins, it will be 0 after halving 15 times, so halving more than 15 times will have the same result as halving 15 times. During the competition, time was urgent, so I did it 20 times to avoid considering edge cases.
Variable explanation
m_vRet[m_iN];//m_vRet[0] The score of each node and descendant node that has not been halved m_vRet[i] The maximum score after halving i times
Code
Core code
classCNeiBo2
{
public:
CNeiBo2(int n, bool bDirect, int iBase = 0):m_iN(n),m_bDirect(bDirect),m_iBase(iBase)
{
m_vNeiB.resize(n);
}
CNeiBo2(int n, vector
{
m_vNeiB.resize(n);
for (const auto & amp; v : edges)
{
m_vNeiB[v[0]- iBase].emplace_back(v[1]- iBase);
if (!bDirect)
{
m_vNeiB[v[1]- iBase].emplace_back(v[0]- iBase);
}
}
}
inline void Add(int iNode1, int iNode2)
{
iNode1 -= m_iBase;
iNode2 -= m_iBase;
m_vNeiB[iNode1].emplace_back(iNode2);
if (!m_bDirect)
{
m_vNeiB[iNode2].emplace_back(iNode1);
}
}
const int m_iN;
const bool m_bDirect;
const int m_iBase;
vector
};
class Solution {
public:
int maximumPoints(vector
m_iK = k;
for (int i = 0; i < m_iN; i + + )
{
m_vRet[i].assign(coins.size(),-1);
}
CNeiBo2 neiBo(coins.size(),edges, false);
dfs(0, -1, 0, neiBo, coins);
return m_vRet[0][0];
}
int dfs(int cur, const int parent, int split,const CNeiBo2 & amp; vNeiBo,const vector & amp; coins)
{
if (split >= 20)
{
return 0;
}
int & amp; iRet = m_vRet[split][cur];
if (-1 != iRet)
{
return iRet;
}
const int curCoin = coins[cur] / (1 << split);
int iType1 = curCoin – m_iK;
{
for (const auto & amp; next : vNeiBo.m_vNeiB[cur])
{
if (parent == next)
{
continue;
}
iType1 + = dfs(next, cur, split, vNeiBo, coins);
}
}
int iType2 = curCoin/2;
{
for (const auto & amp; next : vNeiBo.m_vNeiB[cur])
{
if (parent == next)
{
continue;
}
iType2 + = dfs(next, cur, split + 1, vNeiBo, coins);
}
}
iRet = max(iType1, iType2);
return iRet;
}
int m_iK;
static const int m_iN = 20;
vector m_vRet[m_iN];//m_vRet[0] The score of each node and descendant node that has not been halved m_vRet[i] The maximum score after halving i times
};
Test cases
template
void Assert(const vector & amp; v1, const vector & amp; v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i + + )
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T & t1, const T & t2)
{
assert(t1 == t2);
}
int main()
{
Solution slug;
vector
vector coins;
int k;
int res;
edges = { {0,1},{1,2},{2,3} };
coins = { 10,10,3,3 };
k = 5;
res = slu.maximumPoints(edges, coins,k);
Assert(11, res);
edges = { {0,1},{0,2} };
coins = { 8,4,4 };
k = 0;
res = slu.maximumPoints(edges, coins, k);
Assert(16, res);
//CConsole::Out(res);
}
Extended reading
Video course
Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771
If you want to quickly form a battle and share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses
https://edu.csdn.net/lecturer/6176
Related downloads
If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653
| I am full of positive energy and say it to everyone |
|---|
| It is a good wish to be happy when you hear the flaws. Discover problems early, correct them early, and save your boss money. |
| The origin of the Mohist name: everything is recorded in Mohism. |
| If the program is a one-stop process, then the algorithm is its key point |
Test environment
Operating system: win7 Development environment: VS2019 C++ 17
Or Operating system: win10 Development environment: VS2022 C++ 17
