题解 | #点菜问题#

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<string>
const int MAX = 1024;
struct Dish {
	int price;
	int score;//菜的评价分数
}a[MAX];
int dp[1100][110];
//预算C，菜种类N
int maxScore(int C, int N) {
	//边界
	if (C <= 0) {
		return 0;
	}
	if (N == 0) {
		return 0;
	}
	//核心递推
	if (dp[C][N] != -1)return dp[C][N];
	int i = N;
	for (; i >= 1; i--) {
		if (C >= a[i].price) {//找到买得起的菜
			dp[C][N] = max(maxScore(C, i - 1), maxScore(C - a[i].price, i - 1) + a[i].score);
			return dp[C][N];
		}
	}
	dp[C][N] = 0;
	return 0;
	
}
int main() {
	ios::sync_with_stdio(false);

	int C, N;
	while (cin >> C >> N) {
		memset(dp, -1, sizeof(dp));
		for (int i = 1; i <= N; i++) {
			cin >> a[i].price >> a[i].score;
		}

		cout << maxScore(C, N) << endl;
	}

	return 0;
}