12010번: Landscaping

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

이 문제를 풀기에 앞서 koi 소방차 문제를 풀어보길 추천한다.

1. 각 화단마다 b[i]-a[i] 값만 중요하다. 이 값이 양수이면 흙을 추가해야 하고 음수면 버려야 한다.
2. b[i]-a[i] 값의 절댓값의 개수만큼 해당 위치 i에 1(추가) 혹은 -1(버림)이 있다고 하자.
3. 그러면 문제에 서술된 방법은 1을 없애거나 -1을 없애거나 1과 -1을 동시에 없애는 연산에 대응된다.
4. 소방차 문제 솔루션과 똑같이 여러 개의 층을 만들어서 1이면 층을 증가시키면서, -1이면 감소시키면서 위치(i)와 증감 여부를 저장한다.
5. 소방차 풀이와 마찬가지로 각 층에서 답을 구해서 합해도 최적임이 보장된다.
6. 같은 층에는 1과 -1이 번갈아 존재한다. 짝을 지어 없앨 때는 인접한 쌍의 1과 -1을 없애기만 해도 된다.
7. 각 층마다의 해를 dp로 풀고 답을 합치자.

시간복잡도는 $O(n)$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e5;
int n, x, y, z, c, a[MXN], b[MXN];
long long res;
vector<int> v[MXN * 20];
void f(vector<int> &p) {
    vector<long long> dp(p.size() + 1);
    for (int i = 0; i < p.size(); i++) {
        dp[i + 1] = dp[i] + (a[p[i]] < b[p[i]] ? x : y);
        if (i) dp[i + 1] = min(dp[i + 1], dp[i - 1] + (p[i] - p[i - 1])*z);
    }
    res += dp.back();
}
int main() {
    scanf("%d%d%d%d", &n, &x, &y, &z);
    c = 10 * n;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", a + i, b + i);
        for (int j = a[i]; j < b[i]; j++) v[c++].push_back(i);
        for (int j = a[i]; j > b[i]; j--) v[--c].push_back(i);
    }
    for (int i = 0; i < 20 * n; i++) f(v[i]);
    printf("%lld", res);
    return 0;
}