C++でのジョブスケジュールの最小難易度

毎日少なくとも1つのタスクを完了する必要があります。タスクスケジュールの難易度は、実際にはd日数の各日の難易度の合計です。 1日の難易度は、その日に行われたタスクの最大の難易度です。

したがって、taskDifficultyと呼ばれる整数の配列と整数dがあります。 i番目の仕事の難しさはtaskDifficulty[i]です。タスクスケジュールの最小の難易度を見つける必要があります。タスクのスケジュールが見つからない場合は、-1を返します。

したがって、入力がtaskDifficulty =[6,5,4,3,2,1]、d =2、

1日目は最初の5つのジョブを完了でき、合計難易度は6であるため、出力は7になります。2日目は最後のジョブを完了でき、合計難易度は1なので、スケジュールの難易度は次のようになります。 6 +1=7。

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

• 関数solve（）を定義します。これには、配列v、idx、k、1つの2D dp、

  が必要です。

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

  • 0を返す

• k<0またはidxがvのサイズと同じでk>0の場合、-

  • 1^6を返す

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

  • dp [idx、k]

    を返します

• maxVal：=0

• ret：=inf

• 初期化i：=idxの場合、i

  • maxVal：=v[i]とmaxValの最大値

  • ret：=retとmaxValの最小値+solve（v、i + 1、k --1、dp）

• dp [idx、k]：=ret

• retを返す

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

• n：=jのサイズ

• d> nの場合、-

  • -1を返す

• サイズnx（d + 1）の2D配列dpを1つ定義し、これに-1を入力します

• リターンsolve（j、0、d、dp）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& v, int idx, int k, vector<vector<int> >&
   dp){
      if (idx == v.size() && k == 0)
      return 0;
      if (k < 0 || idx == v.size() && k > 0)
      return 1e6;
      if (dp[idx][k] != -1)
      return dp[idx][k];
      int maxVal = 0;
      int ret = INT_MAX;
      for (int i = idx; i < v.size(); i++) {
         maxVal = max(v[i], maxVal);
         ret = min(ret, maxVal + solve(v, i + 1, k - 1, dp));
      }
      return dp[idx][k] = ret;
   }
   int minDifficulty(vector<int>& j, int d){
      int n = j.size();
      if (d > n)
      return -1;
      vector<vector<int> > dp(n, vector<int>(d + 1, -1));
      return solve(j, 0, d, dp);
   }
};
main(){
   Solution ob;
   vector<int> v = {6,5,4,3,2,1};
   cout << (ob.minDifficulty(v, 2));
}

入力

{6,5,4,3,2,1}, 2

出力

7