电子商务网站有那些功能,卖货平台哪个好,营销网站建设案例,网站建设合同封面模板2023-10-22每日一题
一、题目编号
1402. 做菜顺序二、题目链接
点击跳转到题目位置
三、题目描述
一个厨师收集了他 n 道菜的满意程度 satisfaction #xff0c;这个厨师做出每道菜的时间都是 1 单位时间。
一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间这个厨师做出每道菜的时间都是 1 单位时间。
一道菜的 「 like-time 系数 」定义为烹饪这道菜结束的时间包含之前每道菜所花费的时间乘以这道菜的满意程度也就是 time[i]*satisfaction[i] 。
返回厨师在准备了一定数量的菜肴后可以获得的最大 like-time 系数 总和。
你可以按 任意 顺序安排做菜的顺序你也可以选择放弃做某些菜来获得更大的总和。 示例 1 示例 2 示例 3 提示
n satisfaction.length1 n 500-1000 satisfaction[i] 1000
四、解题代码
class Solution {
public:int maxSatisfaction(vectorint satisfaction) {int n satisfaction.size();vectorvectorint dp(n 1, vectorint(n 1));sort(satisfaction.begin(), satisfaction.end());int res 0;for (int i 1; i n; i) {for (int j 1; j i; j) {dp[i][j] dp[i - 1][j - 1] satisfaction[i - 1] * j;if (j i) {dp[i][j] max(dp[i - 1][j], dp[i][j]);}res max(res, dp[i][j]);}}return res;}
};
五、解题思路
(1) 排序动态规划。
