题解 | #采药#

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
class Herb {
public:
	int time;
	int price;
};
Herb a[100];
int dp[1100][110];
bool CMP(Herb h1, Herb h2) {
	return h1.time < h2.time;
}
//T时间，M种药材可供选择
int maxprice(int T, int M) {
	//边界
	if (M == 0 && T != 0) {
		return 0;
	}
	if (dp[T][M] != -1)return dp[T][M];
	int pos=0;
	for (int i = M; i > 0; i--) {//找到最贵且能采的药
		if (a[i].time <= T) {
			pos = i;
			break;
		}
	}
	if (pos == 0) {
		dp[T][M] = 0;
		return 0;
	}
	dp[T][M] = max(maxprice(T - a[pos].time, pos - 1) + a[pos].price, maxprice(T, pos - 1));
	return dp[T][M];
	
}
int main() {
	ios::sync_with_stdio(false);
	int T, M;
	while (cin >> T >> M) {
		memset(dp, -1, sizeof(dp));
		for (int i = 1; i <= M; i++) {
			cin >> a[i].time >> a[i].price;
		}
		sort(a+1, a + M+1, CMP);
		cout << maxprice(T, M) << endl;


	}
	return 0;
}