C++での最大休暇日数

ある会社が、最高の従業員の1人に、リソースを収集するためにN都市間を移動するオプションを提供したいとします。しかし、従業員は休暇も望んでいます。特定の都市や週で休暇を取ることができます。私たちの仕事は、休暇を取ることができる日数を最大化するように旅行をスケジュールすることですが、従わなければならない特定の規則と制限があります。

• 私たちはN都市間を移動することしかできません。それらは0からN-1までのインデックスで表されます。まず、月曜日に0のインデックスが付けられた都市にいます。

• これらの都市は飛行機で結ばれています。フライトを表すために、1つのN x N行列（必ずしも対称である必要はありません）があります。都市iから都市jへの航空会社のステータスを表すフライト。都市iから都市jへのフライトがない場合、マトリックスflights[i][j]は0になります。それ以外の場合、flights [i] [j] =1です。また、すべてのiについてflights [i] [i]=0です。

• 旅行にはK週間あります。飛行機に乗れるのは1日1回までで、毎週月曜日の朝にしか飛行機に乗れません。

• 都市ごとに、異なる週の休暇日を制限することしかできません。そのため、この関係を示している日と呼ばれるN*Kマトリックスがあります。 days [i] [j]の値は、j​​週目にi市で休暇を取ることができる最大日数を表します。

したがって、フライトマトリックスと日数マトリックスがあり、K週間に取得できる最大の休暇日数を出力する必要がある場合。

したがって、入力がフライト=[[0,1,1]、[1,0,1]、[1,1,0]]の場合、日数=[[1,3,1]、[6,0 、3]、[3,3,3]]の場合、出力は12

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

• n：=フライトの行

• m：=日行列の列

• サイズ（m + 1）x n

  の2D配列dpを1つ定義します。

• 初期化i：=m --1の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • 初期化j：=0の場合、j

    • 初期化k：=0の場合、k

      • jがkと同じであるか、flights [j、k]がゼロ以外の場合、-

        • dp [i、j]：=最大dp [i、j]および日数[j、i] + dp [i + 1、k]

• ret：=dp [0、0]

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

  • Flight [0、i]がゼロ以外の場合、-

    • ret：=retとdp[0、i]

      の最大値

• retを返す

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

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
      int n = flights.size();
      int m = days[0].size();
      vector<vector<int> > dp(m + 1, vector<int>(n));
      for (int i = m - 1; i >= 0; i--) {
         for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
               if (j == k || flights[j][k]) {
                  dp[i][j] = max(dp[i][j], days[j][i] + dp[i + 1][k]);
               }
            }
         }
      }
      int ret = 0;
      ret = dp[0][0];
      for (int i = 1; i < n; i++) {
         if (flights[0][i]) {
            ret = max(ret, dp[0][i]);
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}};
   cout << (ob.maxVacationDays(v1, v2));
}

入力

v1 = {{0,1,1},{1,0,1},{1,1,0}}, v2 = {{1,3,1},{6,0,3},{3,3,3}}

出力

12