วันพักร้อนสูงสุดใน C++

สมมติว่าบริษัทหนึ่งต้องการให้พนักงานที่ดีที่สุดคนหนึ่งมีทางเลือกในการเดินทางไปตามเมืองต่างๆ เพื่อรวบรวมทรัพยากรบางส่วน แต่พนักงานก็ต้องการวันหยุดพักผ่อนเช่นกัน เราสามารถไปพักผ่อนในเมืองหรือสัปดาห์บางเมืองได้ งานของเราคือจัดตารางการเดินทางเพื่อเพิ่มจำนวนวันหยุดพักร้อนที่เราสามารถทำได้ แต่มีกฎและข้อจำกัดบางอย่างที่เราต้องปฏิบัติตาม

• เราสามารถเดินทางได้เฉพาะในเมือง N เท่านั้น พวกมันแสดงด้วยดัชนีตั้งแต่ 0 ถึง N-1 ประการแรก เราอยู่ในเมืองดัชนี 0 ในวันจันทร์

• เมืองเหล่านี้เชื่อมต่อกันด้วยเที่ยวบิน เรามีเมทริกซ์ N x N หนึ่งตัว (ไม่จำเป็นต้องสมมาตร) เพื่อแสดงเที่ยวบิน เที่ยวบินที่แสดงสถานะสายการบินจากเมือง i ไปยังเมือง j. หากไม่มีเที่ยวบินจากเมือง i ไปยังเมือง j ดังนั้นเมทริกซ์เที่ยวบิน[i][j] จะเป็น 0; มิฉะนั้น เที่ยวบิน[i][j] =1 นอกจากนี้ เที่ยวบิน[i][i] =0 สำหรับ i ทั้งหมด

• เรามี K สัปดาห์ที่จะเดินทาง เราขึ้นเที่ยวบินได้ไม่เกินวันละครั้งและขึ้นเที่ยวบินได้เฉพาะเช้าวันจันทร์ของแต่ละสัปดาห์เท่านั้น

• สำหรับแต่ละเมือง เราสามารถจำกัดวันลาพักร้อนในสัปดาห์ต่างๆ ได้เท่านั้น เพื่อที่เราจะได้เมทริกซ์ N*K ที่เรียกว่าวันที่ซึ่งแสดงความสัมพันธ์นี้ สำหรับค่าของ days[i][j] มันหมายถึงจำนวนวันสูงสุดที่เราสามารถพักผ่อนในเมือง i ในสัปดาห์ j

ดังนั้น หากเรามีเมทริกซ์เที่ยวบินและเมทริกซ์วัน และเราจำเป็นต้องส่งออกวันหยุดสูงสุดที่เราสามารถทำได้ในช่วง K สัปดาห์

ดังนั้น หากอินพุตเป็นเหมือนเที่ยวบิน =[[0,1,1],[1,0,1],[1,1,0]], วัน =[[1,3,1],[6,0 ,3,[3,3,3]] จากนั้นผลลัพธ์จะเป็น 12

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=แถวของเที่ยวบิน

• m :=คอลัมน์ของเมทริกซ์วัน

• กำหนดขนาดอาร์เรย์ 2 มิติหนึ่ง dp (m + 1) x n

• สำหรับการเริ่มต้น i :=m - 1 เมื่อ i>=0, อัปเดต (ลด i โดย 1) ให้ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • สำหรับการเริ่มต้น k :=0 เมื่อ k

      • ถ้า j เหมือนกับ k หรือไฟลต์[j, k] ไม่ใช่ศูนย์ ดังนั้น −

        • dp[i, j] :=สูงสุดของ dp[i, j] และวัน[j, i] + dp[i + 1, k]

• ยกเลิก :=dp[0, 0]

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน

  • ถ้าเที่ยวบิน[0, i] ไม่ใช่ศูนย์ ดังนั้น −

    • ret :=สูงสุดของ ret และ dp[0, i]

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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