思路
簡單的01背包裸題(如果不知道什麼是01背包的話去搜一搜),用f[j]表示時間為j時的最優解
需要注意的是如果用一維,第二層循環内的j一定要從大到小逆推。因為當我們枚舉到i,假設此時正在求解f[6],我們需要用帶到上一層的f[3]的值。如果是順序枚舉的話,那麼第i-1層的f[3](也就是不能取第i株草藥的f[3])的值很可能已經被第i層的f[3](也就是能取第i株草藥的f[3])的值所覆寫了(相當于有可能在計算f[6]把第i株草藥采了兩遍,這顯然是不正确的)。但如果是倒序枚舉呢?我們在求解f[6]時,f[7]、f[8]。。。f[t]都處理過了,而f[1]到f[5]還是沒有處理過的,他們此時的值就是i-1層的值,還沒有被第i層的資料所覆寫。那麼求f[6]時,需要用到的i-1層f[3]的值就被完美的儲存下來了。
代碼
#include <iostream>
#include <cstdio>
using namespace std;
int t,m;
int time[],weigh[];
int f[],ans=;
int main()
{
cin>>t>>m;
for (int i=;i<=m;i++){
cin>>time[i]>>weigh[i];
}
for (int i=;i<=m;i++){
for (int j=time[i];j<=t;j++){
f[j]=max(f[j],f[j-time[i]]+weigh[i]);
}
}
cout<<f[t]<<endl;
}