采药 （C语言代码）DP

解题思路:

注意事项:

参考代码:

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <functional> 
#include <iostream>
#include <algorithm>
using namespace std;
const int T=1005, M=105;
int t = 0, m = 0, a[M]={0}, w[M]={0}, dp[M][T];
int main()
{
	scanf("%d%d", &t, &m);
	for(int i = 1; i <= m; ++i)
	{
		scanf("%d%d", &a[i], &w[i]);
	}
	for(int i = 1; i <= m; ++i)
	{
		for(int j = 1; j <= t; ++j)
		{
			if(j >= a[i])
			{
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-a[i]]+w[i]);
			}
			else
			{
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	printf("%d", dp[m][t]);
	return 0;
}