在C++中减少菜肴
假设有个厨师。并且他收集了有关他的n道菜的满意度的数据。厨师可以在1个单位时间内烹饪任何菜肴。菜的喜欢时间系数实际上是花费的时间
烹饪该菜肴(包括以前的菜肴)乘以其满意程度,即时间[i] *满意度[i]。
我们必须找到厨师在准备菜后可以获得的最大喜欢时间系数总和。可以以任何顺序准备菜肴,厨师可以丢弃一些菜肴以获得最大值。
因此,如果输入像[-1,-7,0,6,-7],则输出将为17,除去第二和最后一道菜后,最大总相似时间系数将为-1 * 1 + 0 * 2 + 6 * 3 = 17。
为了解决这个问题,我们将遵循以下步骤-
定义大小为505 x 505的数组dp。
定义一个函数solve(),它将使用idx,时间,数组v,
如果idx与v的大小相同,则-
返回0
如果dp [idx,time]不等于-1,则-
返回dp [idx,时间]
ret:= -inf
ret:=求解(idx + 1,时间,v)和v [idx] *时间+求解(idx + 1,时间+ 1,v)的最大值
dp [idx,time]:= ret
返回ret
从主要方法中执行以下操作-
用dp填充-1
对数组v排序
返回solve(0,1,v)
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>using namespace std;
class Solution {
public:
int dp[505][505];
int solve(int idx, int time, vector <int>& v){
if(idx == v.size()) return 0;
if(dp[idx][time] != -1) return dp[idx][time];
int ret = INT_MIN;
ret = max(solve(idx + 1, time, v), v[idx] * time + solve(idx
+ 1, time + 1, v));
return dp[idx][time] = ret;
}
int maxSatisfaction(vector<int>& v) {
memset(dp, -1, sizeof(dp));
sort(v.begin(), v.end());
return solve(0, 1, v);
}
};
main(){
Solution ob;
vector<int> v = {-1,-7,0,6,-7};
cout << (ob.maxSatisfaction(v));
}
输入项
{-1,-7,0,6,-7}
输出结果
17
以上是 在C++中减少菜肴 的全部内容, 来源链接: utcz.com/z/331574.html