天天看點

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;
}