Chi phí tối thiểu cho vé bằng C ++

Giả sử có một quốc gia phổ biến cho việc đi tàu, chúng tôi đã lên kế hoạch cho chuyến tàu nào đó đi du lịch trước một năm. Chúng tôi có một mảng, đó là tổ chức những ngày trong năm mà chúng tôi sẽ đi du lịch. Mỗi ngày là một số nguyên từ 1 đến 365. Vé tàu được bán theo ba cách khác nhau -

• Vé 1 ngày được bán với giá [0] đô la;

• Vé 1 ngày được bán với giá [0] đô la;

• Vé 30 ngày được bán với giá [2] đô la.

Ở đây các thẻ đi lại cho phép nhiều ngày liên tục. Ví dụ:nếu chúng ta nhận được một vé 7 ngày vào ngày thứ hai, thì chúng ta có thể đi du lịch trong 7 ngày:ngày liên tục (2, 3, 4, 5, 6, 7 và 8). Chúng ta phải tìm số đô la tối thiểu mà chúng ta cần đi hàng ngày trong danh sách ngày đã cho. Vì vậy, nếu đầu vào là [1,4,6,7,8,20] và chi phí là [2,7,15], thì đầu ra sẽ là 11.

Vào ngày 1, chúng tôi đã mua vé 1 ngày với chi phí [0] =2 đô la, tức là bao gồm ngày 1, vào ngày 3, chúng tôi đã mua vé 7 ngày, vì vậy chi phí [1] =7 đô la, tức là bao gồm các ngày từ 3 đến 9 và vào ngày 20, lại mua vé trong 1 ngày, vì vậy chi phí [0] =2 đô la, tức là cho ngày 20. Vì vậy, tổng cộng 11 đô la đã được chi tiêu.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• tạo một mảng có tên là dp, có kích thước 366

• j:=0

• cho tôi trong phạm vi từ 1 đến 366

  • dp [i]:=cost [0] + dp [i - 1]

  • nếu i - 7> =0, thì dp [i]:=tối thiểu của dp [i - 7] + chi phí [1] và dp [i]

  • nếu i - 30> =0, thì dp [i]:=tối thiểu của dp [i - 30] + chi phí [2] và dp [i]

  • nếu j

• trả về dp [365]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int mincostTickets(vector<int>& days, vector<int>& costs) {
      vector <int> dp(366);
      int j = 0;
      for(int i = 1; i < 366; i++){
         dp[i] = costs[0] + dp[i - 1];
         if(i - 7 >= 0){
            dp[i] = min(dp[i - 7] + costs[1], dp[i]);
         }
         if(i - 30 >= 0){
            dp[i] = min(dp[i - 30] + costs[2], dp[i]);
         }
         if(j < days.size() && days[j] == i){
            j++;
         }else
            dp[i] = min(dp[i], dp[i - 1]);
      }
      return dp[365];
   }
};
main(){
   vector<int> v = {1,4,6,7,8,20};
   vector<int> v1 = {2,7,15};
   Solution ob;
   cout << (ob.mincostTickets(v, v1));
}

Đầu vào

[1,4,6,7,8,20]
[2,7,15]

Đầu ra

11