資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的最低票價
假設有一個以火車旅行聞名的國家，我們已經提前一年計劃了一些火車旅行。我們有一個數組，其中包含我們將旅行的年份中的日期。每一天都是從 1 到 365 的整數。火車票以三種不同的方式出售：
1 日票售價為 costs[0] 美元；
1 日票售價為 costs[0] 美元；
7 日票售價為 costs[1] 美元；
30 日票售價為 costs[2] 美元。
這些通行證允許連續旅行這麼多天。例如，如果我們在第 2 天獲得一張 7 日票，那麼我們可以連續旅行 7 天（第 2、3、4、5、6、7 和 8 天）。我們必須找到在給定的日期列表中每天旅行所需的最低美元數。因此，如果輸入類似於 [1,4,6,7,8,20] 並且成本為 [2,7,15]，則輸出將為 11。
在第 1 天，我們購買了 1 日票，價格為 costs[0] = 2 美元，涵蓋第 1 天，在第 3 天，我們購買了 7 日票，因此 cost[1] = 7 美元，涵蓋第 3 天到第 9 天，在第 20 天，再次購買 1 日票，因此 cost[0] = 2 美元，涵蓋第 20 天。因此，總共花費了 11 美元。
為了解決這個問題，我們將遵循以下步驟：
建立一個名為 dp 的陣列，大小為 366
j := 0
對於 i 範圍從 1 到 366
dp[i] := cost[0] + dp[i - 1]
如果 i – 7 >= 0，則 dp[i] := dp[i - 7] + cost[1] 和 dp[i] 的最小值
如果 i – 30 >= 0，則 dp[i] := dp[i - 30] + cost[2] 和 dp[i] 的最小值
如果 j < 天陣列的大小並且 days[j] = i，則將 j 增加 1，否則 dp[i] := dp[i]、dp[i – 1] 的最小值
返回 dp[365]
讓我們看看以下實現以更好地理解：
#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));
}現場演示
[1,4,6,7,8,20] [2,7,15]
輸入
11
更新於：2020 年 5 月 2 日
