점 덮기 (JUNGOL 4826)

https://jungol.co.kr/problem/4826?cursor=MTEsMSwx

---

아이디어

모든 (x,y)는 (|x|,|y|)로 치환할 수 있습니다. 그리고 x좌표 순으로 정렬을 해줍니다. 그리고 점들의 구간을 나누어서 그 구간 내의 점들은 같은 직사각형을 공유하도록 만들면 됩니다. 그러면 문제를 시간내에 해결할 수 있게 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

ll dp[5050]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,x,y;
    vector <pair <ll,ll> > v;
    v.push_back({0,0});

    cin>>N;
    for (i=0;i<N;i++)
    {
        cin>>x>>y;
        v.push_back({abs(x),abs(y)});
    }

    sort (v.begin(),v.end());

    for (i=1;i<=N;i++)
    {
        ll mx=0;
        dp[i]=1e18;
        for (ll j=i;j>=1;j--)
        {
            mx=max(mx,v[j].second);
            dp[i]=min(dp[i],dp[j-1]+mx*v[i].first);
        }
    }

    cout<<dp[N]*4;
}