f455 - 詠竣的哀鳳12

🔗 前往 ZeroJudge 原題

題目描述

題目描述了詠竣想透過打工賺錢購買 iPhone 12 的情境。給定詠竣可打工的時間 T 和 N 個工作機會，每個工作機會有其所需時間 H 和薪水 M。目標是計算詠竣最多能賺到的錢，以及時薪最高的工作內容。

解題思路

本題可以使用動態規劃 (Dynamic Programming) 解決。bp[i] 表示在時間 i 時，詠竣最多能賺到的錢。程式遍歷所有工作機會，並更新 bp 陣列。對於每個工作機會，如果詠竣有足夠的時間完成該工作，則檢查完成該工作後是否能獲得更高的總收入。同時，程式也追蹤時薪最高的工作。

具體來說，程式使用一個迴圈來遍歷每個工作機會。對於每個工作機會，程式檢查是否有足夠的時間來完成它。如果有的話，程式會更新 bp 陣列，以反映完成該工作後可以獲得的最高收入。程式還會追蹤時薪最高的工作，並在找到更高時薪的工作時更新它。

最後，程式輸出詠竣最多能賺到的錢和時薪最高的工作內容。

複雜度分析

• 時間複雜度: O(T * N)，其中 T 是詠竣可打工的時間，N 是工作機會的數量。外層迴圈遍歷 N 個工作，內層迴圈遍歷 T 個時間單位。
• 空間複雜度: O(T)，用於儲存 bp 陣列。

程式碼

#include <iostream>
using namespace std;
int t,n,bp[100001],a,b,ans2;
float ans=0;
string name,nk;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> t >> n;
	while(n--){
		cin >> nk >> a >> b;
		float aa=a,bb=b;
		if(aa/bb>ans){
			ans=aa/bb;
			name=nk;
		}
		for(int i=t-b;i>=0;--i)
			if(bp[i]||i==0)
				bp[i+b]=max(bp[i+b],bp[i]+a);
	}
	for(int i=0;i<=t;++i)
		ans2=max(bp[i],ans2);
	cout << ans2 << "\n" << name ;
}