记录编号	373689	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]采药	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2017-02-21 16:29:45	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
//#define LOCAL
#define is_num(tmp) (tmp<='9'&&tmp>='0')
inline int in()
{
	char tmp(getchar());
	int res(0);
	while(!is_num(tmp))tmp=getchar();
	while(is_num(tmp))
		res=(res<<1)+(res<<3)+(tmp^48),
		tmp=getchar();
	return res;
}
int work(int t,int c);
int T,M;
int v[101],t[101];
int dp[101][1001];
int main()
{
#ifndef LOCAL
	freopen("medic.in","r",stdin);
	freopen("medic.out","w",stdout);
#endif
	memset(dp,-1,sizeof(dp));
	T=in(),M=in();
	for(int i=1;i<=M;++i)
		t[i]=in(),v[i]=in();
	cout<<work(T,M);
}
int work(int TT,int c)
{
	if(c==1)
	{
		if(dp[1][TT]==-1)
		  if(TT>=t[1])dp[1][TT]=v[1];
		  else dp[1][TT]=0;
		return dp[1][TT];
	}
	else
	{
		if(dp[c][TT]!=-1)return dp[c][TT];
		if(TT<t[c])return dp[c][TT]=work(TT,c-1);
		else{
			dp[c][TT]=max(work(TT-t[c],c-1)+v[c],work(TT,c-1));
			return dp[c][TT];
		}
	}
}