b140 - NOIP2005 3.采药

🔗 前往 ZeroJudge 原題

題目描述

題目描述了辰辰需要採藥，目標是在有限的時間內，從多種草藥中選擇，使得採到的草藥總價值最大。每種草藥有其採摘所需的時間和價值。

解題思路

本題可以使用動態規劃解決，類似背包問題。a[i] 表示在時間 i 時可以獲得的最大價值。我們遍歷每種草藥，對於每種草藥，我們嘗試將其加入到背包中，如果加入後價值更大，則更新 a[i+b] 的值，其中 b 是採摘該草藥所需的時間，c 是該草藥的價值。由於時間限制，我們需要從時間較早的狀態推導到時間較晚的狀態。

複雜度分析

• 時間複雜度: O(T * M)
• 空間複雜度: O(T)

程式碼

#include <iostream>
using namespace std;
int main(){
	int t,m;
	cin >> t >> m;
	int a[t+1]={0},b,c,ans=0;
	while(m--){
		cin >> b >> c;
		for(int i=t-b;i>=0;--i){
			if(a[i]||i==0){
				a[i+b]=max(a[i+b],a[i]+c);
				ans=max(a[i+b],ans);
			}
		}
	}
	cout << ans;
}