2300번: 기지국

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

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 1e4;
int n, dp[MAX_N + 1];
pair<int, int> a[MAX_N + 1];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d %d", &a[i].first, &a[i].second);
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        int maxi = 0;
        dp[i] = 1e9;
        for (int j = i; j >= 1; j--) {
            maxi = max(maxi, abs(a[j].second));
            dp[i] = min(dp[i], max(maxi * 2, a[i].first - a[j].first) + dp[j - 1]);
        }
    }
    printf("%d", dp[n]);
    return 0;
}