joj 2526 medic 동적 계획

제목 링크:http://acm.jlu.edu.cn/joj/showproblem.php?pid=2526
제목 의 대의:
                      동굴 안 에는 서로 다른 약초 가 있 는데, 한 포기 한 포기 따 는 데 시간 이 좀 걸 리 고, 한 포기 도 그 자체 의 가치 가 있다.시간 을 드 리 겠 습 니 다. 그 동안 약 초 를 캐 서 얻 은 약초 의 총 가치 가 가장 큽 니 다.
AC 프로그램:
 

#include <iostream>
#include <cstring>
using namespace std;
int a[110], b[110], p[1010][102];

int dp(int shijian, int shanshu){
	if(shijian == 0 ||shanshu == 0)
		return 0;
	if(p[shijian][shanshu] != -1)
		return p[shijian][shanshu];
	int min = -1;
	//          
	int temp = dp(shijian, shanshu - 1);
	min = temp > min ?  temp : min;
	//    ，    
	if(a[shanshu] <= shijian){
		temp = dp(shijian - a[shanshu], shanshu - 1) + b[shanshu];
		min = temp > min ?  temp : min;
	}
	p[shijian][shanshu] = min;
	return min;
}

int main(){
	//freopen("in.txt", "r", stdin);
	int m, n, i;
	while(cin>>m>>n){
		memset(p, -1, sizeof(p));
		for(i = 1; i <= n; i++){
			cin>>a[i]>>b[i];
		}
		cout<<dp(m, n)<<endl;
	}
	return 0;
}