BOJ 2515 전시장

https://www.acmicpc.net/problem/2515

 

출처 : KOI (한국정보올림피아드) 중등부 2012 - 2번

 

대충 요지는, 이전 그림보다 $S$ 이상 높이가 큰 그림만 골라 나가면서 최대의 가격을 얻는 문제.

정렬해놓고 간단한 dp로 풀 수 있다.

$\texttt{dp[i]}$ = $i$번째 그림까지 생각했을 때 얻을 수 있는 최대 가격

이라고 생각하면, 그림을 높이 순으로 정렬한 다음, 

$\texttt{dp[i]}$ 는 $i$번 그림 이전에 올 수 있는 가능성이 있는 $\texttt{dp[u]}$ 에 지금 보는 그림의 가격을 더한 값이거나 (이 경우, $i$번째 그림을 넣는 것이 올바른 답이라는 뜻)

$i-1$번 까지 고려했을 때의 값 (이 경우, $i$번째 그림을 버리겠다는 뜻이다)

두 가지밖에 없고, $u$의 값은 $i$번째 그림의 높이 보다 $S$만큼 작은 가장 높은 그림을 STL의 Upper bound 함수로 찾아 주면 된다.

 

#include <bits/stdc++.h>
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

vector <pii> v;
int dp[303030];
int n,s;
int main()
{
	usecppio
	cin >> n >> s;
	v.reserve(n+1);
	v.push_back({0,0});
	for (int i = 0; i<n; i++)
	{
		int h, c;
		cin >> h >> c;
		v.push_back({h,c});
	}
	sort(all(v));
	for (int i = 1; i<=n; i++)
	{
		int u = upper_bound(all(v),pii(max(v[i].first-s,0),INT_MAX))-v.begin()-1;
		dp[i] = dp[u] + v[i].second;
		dp[i] = max(dp[i],dp[i-1]);
	}
	cout << dp[n];
}