2515, 골드 2

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

2515번: 전시장

문제

• 폭이 같은 그림들을 $n$개 포개어놓는다
• 정면에서 봤을 때 보이는 높이가 $s$이상인 그림들의 값어치의 최대값을 구하라

 

풀이

그림을 정렬하고 
dp 를 이용하여 구한다

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
int n, s;
 
int f(int l, int r, vector<pi>& v)
{
    vector<pi> dp(r-l+1);
    for(int i = l; i <= r; i++) dp[i-l].first = v[i].first;
    dp[0].second = v[l].second;
    for(int i = l+1; i <= r; i++){
        auto it = upper_bound(all(dp), pi(dp[i-l].first-s, 0), [](const pi& me, const pi& parent){
            return me.first < parent.first;
        });
        int cmp = 0;
        if(it - dp.begin() > 0) cmp = (--it)->second;
        dp[i-l].second = max(dp[i-l-1].second, cmp+v[i].second);
    }
    return dp.back().second;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> s;
    vector<pi> v(n);
    for(auto& [h, c]: v) cin >> h >> c;
    sort(all(v));
 
    int ans = 0;
    int l = 0;
    loop(r, n-1){
        if(v[r].first - v[r-1].first >= s){
            ans += f(l, r-1, v);
            l = r;
        }
    }
    ans += f(l, n-1, v);
 
    cout << ans << endl;
 
    return 0;
}cs