在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

回到顶部