BOJ)2300 기지국

문제: icpc.me/2300

모든 건물을 커버하는 기지국들을 세울 때 기지국의 설치비용의 최솟값을 구하는 문제이다.

n이 10000이고 시간 제한이 2초이기 때문에 n^2 dp를 생각해볼 수 있다.

dp[i]= MIN[for(j: 0~i-1) : dp[j]+max(wide[i]-wide[j-1],2*maxheight) ] 라는 점화식이 나온다.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, dp[10010];
pair<ll, ll> a[10010];
int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].first, &a[i].second);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        ll lx = a[i].first;
        ll rx = a[i].first;
        ll y = abs(a[i].second);
        dp[i] = 1e15;
        for (int j = i - 1; j >= 0; j--) {
            ll w = max(abs(rx - lx), 2 * y);
            dp[i] = min(dp[i], dp[j] + w);
            lx = a[j].first;
            y = max(y, abs(a[j].second));
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}