给出一个有向无环图,规定路径是单向且小序号指向大序号,每个节点都有权值。在图上求一条路径使得经过的节点权值和最大,输出路径
[5,10,20,5,4,5],[[1,2],[1,4],[2,4],[3,4],[4,5],[4,6],[5,6]]
"3-4-5-6"
很明显 先去第三点权值为20,再去第四个点权值为5,再去第五个点权值为4,再去第六个点权值为5。这个方案最优
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param potatoNum intvector 依次表示序号为1,2,3..的节点的权值 * @param connectRoad intvector<vector<>> 每个一维数组[x,y]表示从第x号到第y号有路 * @return string */ string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) { const int n = potatoNum.size(); vector<vector<int>> g(n + 1); for (const auto& c : connectRoad) g[c[0]].emplace_back(c[1]); function<pair<int, string>(int)> dfs = [&](int u) { if (memo_.find(u) != end(memo_)) return memo_.at(u); if (g[u].empty()) // leaf node case return memo_[u] = make_pair(potatoNum[u - 1], to_string(u)); string path; int weight = 0; for (const int nxt : g[u]) { auto [w, p] = dfs(nxt); if (w > weight) { path = p; weight = w; } } return memo_[u] = make_pair(potatoNum[u - 1] + weight, to_string(u) + '-' + path); }; string ans; int weight = 0; for (int u = 1; u <= n; ++u) { const auto [w, path] = dfs(u); if (w > weight) { weight = w; ans = path; } } return ans; } private: unordered_map<int, pair<int, string>> memo_; };
string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) { // write code here int dp[251]={0}; int trace[251]; for(int i=0;i<potatoNum.size();i++) { dp[i+1]=potatoNum[i]; trace[i+1]=i+1; } map<int,vector<int>> roads; for(int i=0;i<connectRoad.size();i++) { if(roads.find(connectRoad[i][0])!=roads.end()) //没找到 { roads[connectRoad[i][0]].push_back((connectRoad[i][1])); } else { vector<int> one; one.push_back(connectRoad[i][1]); roads[connectRoad[i][0]]=one; } } int ans=dp[potatoNum.size()]; int index=potatoNum.size(); for(int i=potatoNum.size();i>=1;i--) { if(roads.find(i)==roads.end())//没有下一条 { if(dp[i]>ans) { ans=dp[i]; index=i; } } else { int max_=0; int next=0; for(int k=0;k<roads[i].size();k++) { if(max_<dp[roads[i][k]]) { max_=dp[roads[i][k]]; next=roads[i][k]; } } dp[i]+=max_; trace[i]=next; //记录下下一条位置 if(dp[i]>ans) { ans=dp[i]; index=i; } } } //从index处往后迭代 string res; while(trace[index]!=index) { res+=to_string(index); res+='-'; index=trace[index]; } res+=to_string(index); return res; }
class Solution { public: /** * * @param potatoNum int整型vector 依次表示序号为1,2,3..的番薯洞各有多少个番薯 * @param connectRoad int整型vector<vector<>> 每个一维数组[x,y]表示从第x号番薯洞到第y号有路 * @return string字符串 */ string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) { // write code here int sz = potatoNum.size(); vector<vector<int> > path(sz +1); // 存路径,从后往前存 for(auto e: connectRoad){ path[e[1]].push_back(e[0]); } vector<pair<int,int>> dp(sz+1); // 每个节点 可摘取的最大数量,以及路径的前一个节点 dp[0] = {0,0}; for(int i=1;i<sz+1;i++){ pair<int,int> Maxtemp = {0,0}; for(int j=0;j<path[i].size();j++){ if(dp[path[i][j]].first > Maxtemp.first){ Maxtemp.first = dp[path[i][j]].first; Maxtemp.second = path[i][j]; } } dp[i] = {Maxtemp.first+potatoNum[i-1],Maxtemp.second}; } int maxnum = 0; //最大可采摘数量 int maxindex = 0; // 最大可采摘数量对应的节点 for(int i = 0;i<sz+1;i++){ if(dp[i].first>maxnum){ maxnum = dp[i].first; maxindex = i; } } vector<int> resint; while(maxindex!=0){ resint.push_back(maxindex); maxindex = dp[maxindex].second; } string res; for(int i =resint.size()-1;i>=0;i--){ string s = to_string(resint[i]); res.append(s); if(i!=0){ res.append("-"); } } return res; } };
//该方法遍历深度较大,所以只过了80%,剩下的超时了,实在想不出哪里可以剪枝 //望大佬提供一下剪枝四路 class Solution { public: void find(vector<int>& potatoNum, vector<vector<int> >& connectRoad,int i,int tmp) { tmp+=potatoNum[i - 1];//累加到达当前洞口中的番茄个数 part.push_back(i);//存入当前路劲 //循环遍历找当前洞口联通的下一个洞口 for(int k = 0;k<connectRoad.size();k++) { if(connectRoad[k][0] == i)//找到了 find(potatoNum,connectRoad,connectRoad[k][1],tmp);//进入该洞口 } //当走到这里时,表示到达了当前路劲的尽头,判断当前路劲下取得番茄个数是否大于 //max,如果大于,则番茄个数交换,最佳路径交换 if(tmp > max) { best_part = part; max = tmp; } //当前路劲返回上一层,继续寻找下一个联通的洞穴 part.pop_back(); } string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) { // write code here //分别从每个洞口开始找 for(int i = 1;i<potatoNum.size() + 1;i++) { find(potatoNum,connectRoad,i,0); } //以下是返回string string str(""); for(int i = 0;i<best_part.size();i++) { int tmp = best_part[i]; stringstream ss; ss<<tmp; str+=ss.str(); if(i != best_part.size() - 1) str+="-"; } return str; } public: vector<int> part;//当前路径 vector<int> best_part;//取得最多番茄个数的路径 int max = 0;//番茄最多个数 };