题解 | #采药#

//经典的0-1背包问题
#include "stdio.h"
#include "algorithm"
using namespace std;
int T,M;//T为总时间，M为草药株树
int plantTime[110];
int val[110];
int bag[110][1010];

void Init(){//构造背包的动态规划二维数组
    for (int i = 0; i <= M; ++i) {
        for (int j = 0; j <= T; ++j) {
            if(i == 0 || j == 0){
                bag[i][j] == 0;
                continue;
            }
            if(plantTime[i] > j){
                bag[i][j] = bag[i-1][j];
            } else{
                bag[i][j] = max(bag[i-1][j],bag[i-1][j-plantTime[i]]+val[i]);
            }
        }
    }
}

int main(){
    while (scanf("%d%d",&T,&M)!=EOF){
        for (int i = 1; i <= M; ++i) {
            scanf("%d%d",plantTime+i,val+i);
        }
        Init();
        printf("%d\n",bag[M][T]);
    }
}