L2-043 龙龙送外卖 贪心+记忆化搜索

题目详情 - L2-043 龙龙送外卖 (pintia.cn)

这题题目不好理解。

思路：由于最后不用返回外卖点，通过手动模拟最短路径可以发现贪心策略就是：在最大深度那里不要返回会使总距离最小，而其他点都需要计算返回到上个访问到的点或根节点的两倍距离。那么答案就是：总距离-最大深度。

每次添加订单都可能会导致这里的最大深度发生变化，所以这里就有点像dp。

1.  
   #include<iostream>
2.  
   using namespace std;
3.  
   const int N = 100010;
4.  
   int t[N], dis[N], maxl, root = -1;
5.  
    
6.  
   int dfs(int x,int d){
7.  
   if(t[x] == -1 || dis[x]){//根节点或当前结点已经访问过
8.  
   maxl = max(maxl,d dis[x]);
9.  
   return d*2;
10.  
    }
11.  
    int res = dfs(t[x],d 1);
12.  
    dis[x] = dis[t[x]] 1;
13.  
    return res;
14.  
    }
15.  
     
16.  
    int main(){
17.  
    cin.tie(0)->sync_with_stdio(false); cout.tie(0);
18.  
    int n,m; cin>>n>>m;
19.  
    for(int i = 1; i <= n; i ) cin>>t[i];
20.  
    int sum = 0;
21.  
    while(m--){
22.  
    int x; cin>>x;
23.  
    sum = dfs(x,0);
24.  
    cout<<sum-maxl<<endl;
25.  
    }
26.  
    return 0;
27.  
    }

这篇好文章是转载于：学新通技术网