c++刷leetcode（1402. 做菜顺序）【回溯+贪心算法思想】

糖逗

题目描述：

1. 
   
2. 一个厨师收集了他 n 道菜的满意程度 satisfaction ，这个厨师做出每道菜的时间都是 1 单位时间。
   
3. 
   
4. 一道菜的 「喜爱时间」系数定义为烹饪这道菜以及之前每道菜所花费的时间乘以这道菜的满意程度，也就是 time[i]*satisfaction[i] 。
   
5. 
   
6. 请你返回做完所有菜 「喜爱时间」总和的最大值为多少。
   
7. 
   
8. 你可以按 任意 顺序安排做菜的顺序，你也可以选择放弃做某些菜来获得更大的总和。
   
9. 
   
10. 
    
11. 
    
12. 示例 1：
    
13. 
    
14. 输入：satisfaction = [-1,-8,0,5,-9]
    
15. 输出：14
    
16. 解释：去掉第二道和最后一道菜，最大的喜爱时间系数和为 (-1*1 + 0*2 + 5*3 = 14) 。每道菜都需要花费 1 单位时间完成。
    
17. 示例 2：
    
18. 
    
19. 输入：satisfaction = [4,3,2]
    
20. 输出：20
    
21. 解释：按照原来顺序相反的时间做菜 (2*1 + 3*2 + 4*3 = 20)
    
22. 示例 3：
    
23. 
    
24. 输入：satisfaction = [-1,-4,-5]
    
25. 输出：0
    
26. 解释：大家都不喜欢这些菜，所以不做任何菜可以获得最大的喜爱时间系数。
    
27. 示例 4：
    
28. 
    
29. 输入：satisfaction = [-2,5,-1,0,3,-3]
    
30. 输出：35
    
31. 
    
32. 
    
33. 提示：
    
34. 
    
35. n == satisfaction.length
    
36. 1 <= n <= 500
    
37. -10^3 <= satisfaction[i] <= 10^3

复制代码

1. void dfs(vector<int>&input,vector<int>&visit, int cur, int& res, int temp, int len){
   
2.         if(cur >= input.size()){
   
3.             res = max(res, temp);
   
4.             return;
   
5.         }
   
6.         
   
7.         if(visit[cur] == 0){
   
8.             int store = cur;
   
9.             visit[cur] = 1;
   
10.             temp+=len*input[cur];
    
11.             dfs(input, visit, cur+1, res, temp, len+1);
    
12.             temp-=len*input[store];
    
13.             visit[store] = 0;
    
14.         }
    
15.             
    
16.     }
    
17.     int maxSatisfaction(vector<int>& satisfaction) {
    
18.         sort(satisfaction.begin(), satisfaction.end());
    
19.         int len = satisfaction.size();
    
20.         int res = 0;
    
21.         for(int i = 0; i < len ; i++){
    
22.             vector<int> visit(len, 0);
    
23.             dfs(satisfaction,visit, i, res, 0, 1);
    
24.             cout <<res <<endl;
    
25.         }
    
26.         
    
27.         return res;
    
28.         
    
29.     }

复制代码