[白俊17845]コース

質問:17845課
タイプ:DP、リュックの問題
考え方:平凡な問題
最大学習時間を超えない場合は、最も重要な科目を選択します.
コード#コード#

#include <bits/stdc++.h>
using namespace std;

#define fastio cin.tie(0); ios::sync_with_stdio(false);
int N, K;
pair<int, int> arr[1001];
int dp[10001][1001];

int dfs(int d, int cnt) {
	if (d == K) return 0;

	int& ret = dp[cnt][d];
	if (ret != -1) return ret;
	ret = 0;

	if (cnt + arr[d].first <= N) ret = max(ret, dfs(d + 1, cnt + arr[d].first) + arr[d].second);
	ret = max(ret, dfs(d + 1, cnt));

	return ret;
}

int main() {
	fastio
	cin >> N >> K;

	for (int i = 0; i < K; i++) cin >> arr[i].second >> arr[i].first;

	memset(dp, -1, sizeof(dp));
	cout << dfs(0, 0);

	return 0;
}