先上題目鏈接:P1616 瘋狂的采藥
然后放AC代碼:
#include<bits/stdc++.h> #define ll long long using namespace std; ll f[100010]; ll timee[10010]; ll w[10010]; int main() {ll t,m;cin>>t>>m;//t總時間,m總草藥//time時間,w價值for(ll i=1;i<=m;i++){scanf("%lld",&timee[i]);scanf("%lld",&w[i]);}for(ll i=1;i<=m;i++)for(ll j=timee[i];j<=t;j++){f[j]=max(f[j],f[j-timee[i]]+w[i]);}cout<<f[t]<<endl; }
然后推薦一道類似的題目:采藥
不同點在與這題是完全背包,采藥那題是01背包,
還有就是瘋狂的采藥數據比較大,建議用滾動數組,如果用二維數組不知道會不會不行,我沒試過.
然后講一下思路:
假定你已經學過滾動數組和01背包了,那么這題就很簡單了,相對于普通的01背包來說,如果用滾動數組的話,
對于for的第二維也就是代表剩余空間那一維是從大到小遍歷的,這樣就能防止每個物品放了超過一次以上,
也就是新數據覆蓋舊數據后在這次循環中新數據不會被再覆蓋,放在實際層面就是一個物品只能被放一次
?
如果現在把for的第二維也就是代表剩余空間那一維是從小到大遍歷,那么新數據也可能被覆蓋,也就是一個物品放了后還可能接著放,
這樣一來就從01背包轉移到完全背包了
?
至于能用滾動數組的原因是第i層只和第i-1層有關
?
