在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