动态规划——疯狂的采药

01背包的另一种形式，这里我们只需要将上面的倒序改成正序即可(还是从w[i]截断)

#define _CRT_SECURE_NO_WARNINGS
#include 
#define rep(i,s,n) for(long long i=s;i=d;i--)
using namespace std;
const int SIZE = 10000005;
struct data
{
	long long t;
	long long m;
};
struct data herb[10001];
long long tt, temp;
long long dp[SIZE];

signed main()
{
	ios::sync_with_stdio(false);
	memset(dp, 0, sizeof(dp));
	cin >> tt >> temp;
	rep(i, 0, temp)
		cin >> herb[i].t >> herb[i].m;
	long long now = tt;

	rep(i, 0, temp)
	{
		rep(j, herb[i].t, tt + 1)
		{
			dp[j] = max(dp[j], dp[j - herb[i].t] + herb[i].m);

		}
	}
	cout << dp[tt];

	return 0;

}

1 0 7 10^7 107应该是有7个0

一定要开long long !!!