在C++中减少菜肴
假设有个厨师。并且他收集了有关他的n道菜的满意度的数据。厨师可以在1个单位时间内烹饪任何菜肴。菜的喜欢时间系数实际上是花费的时间
烹饪该菜肴（包括以前的菜肴）乘以其满意程度，即时间[i]*满意度[i]。
我们必须找到厨师在准备菜后可以获得的最大喜欢时间系数总和。可以以任何顺序准备菜肴，厨师可以丢弃一些菜肴以获得最大值。
因此，如果输入像[-1，-7,0,6，-7]，则输出将为17，除去第二和最后一道菜后，最大总相似时间系数将为-1*1+0*2+6*3=17。
为了解决这个问题，我们将遵循以下步骤-
定义大小为505x505的数组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