백준[2296] 건물짓기

문제 설명

문제 링크

http://icpc.me/2296

2296번: 건물짓기

풀이

dp로 풀 수 있다.

dp[i][0] = i번째까지 1,3 사분면을 사용하여 최댓값, dp[i][1] = i번째까지 2, 4 사분면을 사용하여 최댓값

위의 정의대로 구현하면 된다. 

코드

#include <iostream>
#include <algorithm>

using namespace std;

struct T { int x, y, c; };
vector<T> v;
int dp[1003][2];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y, c; cin >> x >> y >> c;
        v.push_back({x, y, c});
    }

    sort(v.begin(), v.end(), [](T &a, T &b) { return a.x < b.x; });
    int ret = 0;
    for (int i = 0; i < n; i++) dp[i][0] = dp[i][1] = v[i].c;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (v[j].y < v[i].y) dp[i][0] = max(dp[i][0], dp[j][0] + v[i].c);
            if (v[j].y > v[i].y) dp[i][1] = max(dp[i][1], dp[j][1] + v[i].c);
        }
        ret = max({ret, dp[i][0], dp[i][1]});
    }
    printf("%d", ret);
}