编写题解 1100: 采药

解题思路:
1把大问题转换成小问题，然后递归.

2写出最小问题的初始状态。

3用一个数组记录各层问题的中间计算结果，避免重复计算。

参考代码:

#include <stdio.h>
#include <stdlib.h>

int memo[101][1001];

int fun(int t[],int v[],int T,int M)
{
	
	int mv0,mv1;
	if(memo[M][T] >=0){
		return memo[M][T];
	}
	
	if(T == 0){
		memo[M][T] = 0;
		return 0;
	}
	if(M == 1){
		if(t[1] > T){
			memo[M][T] = 0;
			return 0;
		}else{
			memo[M][T] = v[1];
			return v[1];
		}
	}
	
	mv0 = fun(t,v,T,M-1);
	if(t[M] > T){
		memo[M][T] = mv0;
		return mv0;
	}
	mv1 = fun(t,v,T-t[M],M-1) + v[M];
	if(mv0 > mv1) {
		memo[M][T] = mv0;
		return mv0;
	}else{
		memo[M][T] = mv1;
		return mv1;
	}
}



int main()
{
	int T,M;
	int t[101];
	int v[101];
	int i,j;
	int mv;
	
	for(i = 0;i<101;i++){
		for(j = 0;j<1001;j++){
			memo[i][j] = -1;
		}
	}
	
	scanf("%d%d",&T,&M);
	
	for(i = 1;i <=  M;i++){
		scanf("%d%d",&t[i],&v[i]);
	}
	
	mv = fun(t,v,T,M);
	
	printf("%d\n",mv);
	
	
	
	
	
	return 0;
}