NOIP 2005普及組 采藥 詳解

思路

簡單的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;
}