C++でk日間にわたって仕事を完了するための困難の最小合計を見つけるためのプログラム

ジョブと呼ばれる数値のリストと別の値kがあるとします。今、私たちはすべての仕事をkの異なる日に終えたいと思っています。ジョブは指定された順序で実行する必要があり、毎日1つのタスクを完了する必要があります。ジョブiの難易度はjobs[i]に保存され、1日のジョブのリストを完了する難易度は、その日に実行される最大の難易度のジョブになります。したがって、k個の異なる日にジョブを実行するための難しさの最小合計を見つける必要があります。

したがって、入力がjobs =[2、3、4、6、3] k =2のような場合、出力は8になります。最初に[2]を実行し、次に[3、4、6、3]を実行します。したがって、難易度は2 +最大（3、4、6、3）=8です。

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

• サイズが505x15の配列dpを定義します。
• 関数dfs（）を定義します。これには、start、k、および配列vが必要です。
• 開始>=vのサイズの場合、-
  • return（kが0と同じ場合は0、それ以外の場合はinf）
• k <0の場合、-
  • return inf
• dp [start、k]が-1に等しくない場合、-
  • return dp [start、k]
• ret：=inf
• val：=0
• iを初期化する場合：=開始、i
• val：=valとv[i]の最大値
• ret：=retの最小値と（val + dfs（i + 1、k --1、v））

例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e6;
int dp[505][15];
int dfs(int start, int k, vector <int>& v){
   if(start >= v.size()){
      return k == 0 ? 0 : inf;
   }
   if(k < 0)
      return inf;
   if(dp[start][k] != -1)
      return dp[start][k];
   int ret = inf;
   int val = 0;
   for(int i = start; i < v.size(); i++){
      val = max(val, v[i]);
      ret = min(ret, val + dfs(i + 1, k - 1, v));
   }
   return dp[start][k] = ret;
}
int solve(vector<int>& jobs, int k) {
   memset(dp ,-1, sizeof dp);
   return dfs(0, k, jobs);
}
int main(){
   vector<int> v = {2, 3, 4, 6, 3};
   int k = 2;
   cout << solve(v, k);
}

入力

{2, 3, 4, 6, 3}, 2

出力

8