BOJ 29792 - 규칙적인 보스돌이

체감티어: G5

태그: 냅색, dp, 브루트포스

 

제 1회 임스의 메이플컵의 C번이다. 냅색은 구원자이다.

 

---

일단 n명중 m명을 뽑아 15분간 보스를 잡고 m명이 얻은 값을 최대화 하면 되는 간단한 문제이다. 뭔가 dp냄새가 난다. 하지만 테이블을 어떻게 잡아야 할지 잘 모르겠다. 일단 15분은 900초이므로 900칸의 배열을 생성하면 준비는 끝난다. 문제는 각 캐릭터마다 초당 데미지가 다르다. 하지만 보스의 체력과 초당 데미지 사이에 관계를 Wi로 보고, 보스를 잡고 주는 값을 Ci로 보면 단순한 냅색의 형태가 나온다. i번째 보스를 잡는데 걸리는 시간은 (보스의 체력 / 초당 데미지)의 올림으로 나타낼 수 있다. 이를 각 캐릭터마다 따로 적용하고 냅색을 한 결과의 합을 구하면 된다.

 

#define _CRT_SECURE_NO_WARNING
#include <bits/stdc++.h>
#include <cassert>
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define repair(x) x.erase(unique(all(x)),x.end())
using namespace std;
typedef long long ll; //long long. or use int64_t
typedef long double ld; //long double
const int iinf = 1e9; //integer maximum
const long long linf = 1e18; //long long maximum
const int mod = 1e9 + 9; //prime number
template<class T>T gcd(T x, T y) { if (!y)return x; return gcd(y, x % y); }
template<class T>T lcm(T x, T y) { return (x * y) / gcd(x, y); }
int main() {
	fastio;
	int n, m, k;
	cin >> n >> m >> k;
	vector<ll>arr(n);
	for (auto& v : arr)cin >> v;
	vector<pair<ll, ll>>mon(k);
	for (auto& v : mon)cin >> v.first >> v.second;
	sort(all(arr), greater<ll>());
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		if (!m)break;
		m--;
		vector<ll>save(k+1), dp(909);
		for (int j = 0; j < k; j++) {
			save[j + 1] = mon[j].first % arr[i] ? mon[j].first / arr[i] + 1 : mon[j].first / arr[i];
		}
		for (int j = 1; j <= k; j++) {
			for (int w = 900; w >= 1; w--) {
				if (save[j] <= w) {
					dp[w] = max(dp[w], dp[w - save[j]] + mon[j - 1].second);
				}
			}
		}
		ans += dp[900];
	}
	cout << ans;
	return 0;
}