题解 | #采药#

#include <bits/stdc++.h>
#include <vector>
using namespace std;
//定义一个草药的结构体
struct st{
    int Time;//采这个草药的时间
    int value;//这个草药的价值
};
int main() {
    int time,type;//你所拥有的时间以及草药的种类
    st one;
    while(cin>>time>>type)
    {
        vector<st> s;//存储草药的采摘耗时以及价值
        int maxvalue=0;//我们能够获得的最大的价值
        for(int i=0;i<type;i++)
        {
            cin>>one.Time>>one.value;
            s.push_back(one);
        }
        //dp[i]的意思是i的时间最多可以获取多少价值
        vector<int> dp(1001,0);
        for(int i=0;i<type;i++)//先遍历物品
        {
            for(int j=time;j>=1;j--)//再遍历背包，注意从大到小
            {
                if(j-s[i].Time>=0)//如果够装，再选择装or不装
                    dp[j]=max(dp[j],dp[j-s[i].Time]+s[i].value);
                maxvalue=max(maxvalue,dp[j]);//随时更新maxvalue
            }
        }
        cout<<maxvalue<<endl;
    }
}
// 64 位输出请用 printf("%lld")