leetcode_1402 做菜顺序

本文主要是介绍leetcode_1402 做菜顺序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题意

给定一个数组sa，你可以任意选取其中的元素进行排列。

求舒适值得最大值。

舒适值定义为$ans={\sum }_{i=0}^k(i+1)\ast s{a}_i$

做菜顺序

2. 题解

2.1 贪心 + 前缀和

我们在sa中选取元素时，需要进行排序。

为了使得ans的值最大，我们需要将较大的$s{a}_i$值与较大的$i$相乘。

若$\forall s{a}_i\ge 0,0\le i\le sa.size()$

则我们直接选取所有元素即可，但是$sa$中存在负数。

我们需要比较添加一个负数带来的收益是否为正。

我们可以从大到小进行排序得到序列$a$，这样会很方便进行计算，每次添加一个新元素$a_k$对原有序列增

加的收益为

$inc=su{m}_{i=0}^k{a}_i$
即前缀和
$PrefixSum(a,k+1)$

当$inc>0$时，我们继续添加元素。
当$inc<=0$时，退出。

• 代码

class Solution {
public:int maxSatisfaction(vector<int>& satisfaction) {sort(satisfaction.rbegin(), satisfaction.rend());int sz = satisfaction.size();int res = 0;int prefix = 0;for ( int i = 0; i < sz; ++i) {if (prefix + satisfaction[i] > 0) {res += prefix + satisfaction[i];prefix += satisfaction[i];}else break;}return res;}
};

2.2 动态规划

排序一下，每道菜都可以选择做或者不做，变成了一个0-1背包的问题。

用dp[i][j]表示前i个菜，选择j道菜的最大收益。

$$dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+i\ast satification[j])$$

需要排序的解释直接看官解了

class Solution {
public:int maxSatisfaction(vector<int>& satisfaction) {sort(satisfaction.begin(), satisfaction.end());int sz = satisfaction.size();vector<vector<int>> dp(sz + 1, vector<int>(sz + 1));int res;for ( int i = 1; i <= sz; ++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;}
};

这篇关于leetcode_1402 做菜顺序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---