AtCoder Regular Contest 042 C - おやつ

問題

C: おやつ - AtCoder Regular Contest 042 | AtCoder

解法

値段降順におやつをソートして、
dp[i][j]=i番目までのおやつから選んで値段の合計がjのときの満足度の最大
というDPをする。
答えは、DPの各状態の一番最後に選んだおやつがi番目であるであると思い込んで最大を取る。DPの過程も含め全て見れば、どこかに最大値が存在する。

実装

最初は三分探索しようとしていた。

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int MAX_N = 5000, MAX_P = 5000;
 
struct Oyatsu
{
	int a, b;
	bool operator < (const Oyatsu &o) const
	{
		return a > o.a;
	}
};
 
int N, P;
Oyatsu oyatsu[MAX_N];
int dp[MAX_N + 1][MAX_P + 101];
 
signed main()
{
	cin >> N >> P;
	for (int i = 0; i < N; i++)
	{
		cin >> oyatsu[i].a >> oyatsu[i].b;
	}
	sort(oyatsu, oyatsu + N);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j <= P + 100; j++)
		{
			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
			if (j + oyatsu[i].a <= P + 100)
				dp[i + 1][j + oyatsu[i].a] = max(dp[i + 1][j + oyatsu[i].a], dp[i][j] + oyatsu[i].b);
		}
	}
	int ans = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j <= P + oyatsu[i - 1].a; j++)
		{
			ans = max(ans, dp[i][j]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}