题目描述

采药（优化）

样例

#include<iostream>
#include<vector>

struct Herb {
    int value;
    int time;
};

int maxValueInTheHerbs(Herb[], int, int);

int main()
{
    Herb Herbs[1000];

    int t, m;

    std::cin>>t>>m;

    for(int i=0; i<m; ++i) {
        std::cin>>Herbs[i].time>>Herbs[i].value;
    }

    std::cout<<maxValueInTheHerbs(Herbs, t, m);

    return 0;
}

inline int cmp(int first, int second)
{ return first>second?first:second; }

int maxValueInTheHerbs(Herb array[], int time, int howManyHerbs)
{
    int f[101]={0};

    for(int i=1; i<=howManyHerbs; ++i) {
        for(int j=time; j>=array[i].time; --j) {
            f[j] = cmp(f[j], f[j-array[i].time]+array[i].value);
        }
    }
    return f[time];
}