home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

วันหยุดสูงสุดใน C++

ปัญหา

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

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

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

เช่น ถ้าผนวกเขาเป็น flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]] ผลลัพธ์จะเป็น 12

วิธีแก้ปัญหา

  1. n := จำนวนแถวของ flights
  2. m := จำนวนคอลัมน์ของเมทริกซ์ days
  3. กำหนดอาร์เรย์ 2D dp ขนาด (m+1) x n
  4. for i := m-1 ถึง 0 (ลดทีละ 1) ทำ:
    • for j := 0 ถึง n-1 ทำ:
      • for k := 0 ถึง n-1 ทำ:
        • ถ้า j เท่ากับ k หรือ flights[j][k] ไม่เป็น 0 แล้ว:
          • dp[i][j] := max(dp[i][j], days[j][i] + dp[i+1][k])
  5. ret := dp[0][0]
  6. for i := 1 ถึง n-1 ทำ:
    • ถ้า flights[0][i] ไม่เป็น 0 แล้ว: ret := max(ret, dp[0][i])
  7. คืนค่า ret

ตัวอย่างโค้ด C++

#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; 
    } 
}; 

int 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