e637 - 10465 - Homer Simpson
題目描述
題目要求在給定的時間 t 內，荷馬可以吃到的 Krusty 漢堡和 Kwik-e-Mart 漢堡的最大數量，其中吃一個 Krusty 漢堡需要 m 分鐘，吃一個 Kwik-e-Mart 漢堡需要 n 分鐘。如果無法完全利用時間，則需要輸出浪費的時間。
解題思路
這題可以使用動態規劃的思想來解決。我們可以建立一個陣列 a，其中 a[i] 表示在 i 分鐘內可以吃到的最大漢堡數。初始化 a[0] = 1，表示在 0 分鐘內可以吃 0 個漢堡。然後，我們遍歷所有可能的 Krusty 漢堡數量，並更新 a 陣列。接著，遍歷所有可能的 Kwik-e-Mart 漢堡數量，再次更新 a 陣列。最後，檢查 a[t] 是否為 0。如果為 0，表示無法完全利用時間，則需要從 t-1 開始向後搜索，找到第一個 a[i] 大於 0 的位置，並輸出 a[i]-1 和 t-i。
複雜度分析
- 時間複雜度: O(t)
- 空間複雜度: O(t)
程式碼
#include <iostream>
using namespace std;
int main(){
int m,n,t;
while(cin >> m >> n >> t){
int a[t+1]={0};
a[0]=1;
for(int i=0,tm=t-m;i<=tm;++i){
if(a[i]){
int im=i+m;
a[im]=max(a[i]+1,a[im]);
}
}
for(int i=0,tn=t-n;i<=tn;++i){
if(a[i]){
int in=i+n;
a[in]=max(a[i]+1,a[in]);
}
}
if(a[t]){
cout << a[t]-1 << "\n";
}
else{
for(int i=t-1;i>=0;--i)
if(a[i]){
cout << a[i]-1 << " " << t-i << "\n";
break;
}
}
}
}