C++での料理の削減

シェフがいるとします。そして、彼は彼のn個の料理の満足度に関するデータを収集しました。シェフは1単位時間でどんな料理でも調理できます。料理の時間係数は実際にはかかった時間です

以前の料理に満足度を掛けた料理を含むその料理を調理するSotime[i]*successfaction[i]。

シェフが料理の準備後に取得できるLike-time係数の最大合計を見つける必要があります。料理は任意の順序で準備でき、シェフはこの最大値を得るためにいくつかの料理を捨てることができます。

したがって、入力が[-1、-7,0,6、-7]の場合、出力は17になります。2番目で最後の皿を削除した後、最大合計類似時間係数は-1 *1+になります。 0 * 2 + 6 *3=17。

これを解決するには、次の手順に従います-

• サイズの配列dpを定義します：505x505。

• 関数solve（）を定義します。これには、idx、時間、配列v、

  が必要です。

• idxがvのサイズと同じである場合、-

  • 0を返す

• dp [idx、time]が-1に等しくない場合、-

  • dp [idx、time]

    を返します

• ret：=-inf

• ret：=solve（idx + 1、time、v）およびv [idx]*時間+solve（idx + 1、time + 1、v）の最大値

• dp [idx、time]：=ret

• retを返す

• メインの方法から、次のようにします-

• この-1をdpで埋めます

• 配列を並べ替える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