티스토리 뷰

알고리즘 관련/BOJ

BOJ)2300 기지국

JASON 자손9319 2017. 7. 25. 18:14

문제: 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) ] 라는 점화식이 나온다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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), * 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13511 트리와 쿼리2  (0) 2017.07.31
BOJ)14657 준오는 최종인재야!!  (0) 2017.07.29
BOJ)2300 기지국  (0) 2017.07.25
BOJ)11985 오렌지 출하  (0) 2017.07.24
BOJ)10637 Minimum Spanning Tree  (0) 2017.07.21
BOJ)2261 가장 가까운 두 점  (1) 2017.07.09
댓글
댓글쓰기 폼