题解 | #采药#

//标准的0/1背包，模板题
#include<iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include<vector>
using namespace std;

const int MAXN = 120;
int t_cost[MAXN];
int value[MAXN];
int dp_result[120][1200];

int dp(int m, int t)
{
	if (m == -1||t==0)
	{
		return 0;
	}
	else if (dp_result[m][t] != 0)
	{
		return dp_result[m][t];
	}
	else
	{
		if (t >= t_cost[m])
		{

			dp_result[m][t] = max(dp(m - 1, t), dp(m - 1, t - t_cost[m])+value[m]);
			return dp_result[m][t];
		}
		else
		{
			dp_result[m][t] = dp(m - 1, t);
			return dp_result[m][t];
		}
	}
}
int main() 
{
	fill(dp_result[0], dp_result[0] + 120 * 1200, 0);
	int T, M;
	scanf("%d %d", &T, &M);
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &t_cost[i], &value[i]);

	}
	cout << dp(M - 1, T);


}