백준27491 Sum Over Zero

작성일 | In

문제 링크

  • https://icpc.me/27491

사용 알고리즘

  • DP
  • 세그먼트 트리

시간복잡도

  • $O(N \log N)$

풀이

누적 합 배열을 이용하면 구간에 포함되 수들의 합이 0 이상이 되는지 빠르게 판별할 수 있습니다. $S_r - S_{l-1} \geq 0$인지 판별하면 되므로 $S_r \geq S_{l-1}$인지 판별하면 됩니다.

점화식은 어렵지 않게 세울 수 있습니다. $D(n) = \max\left{ D(n-1), D(i) + n - i \texttt{ when } 0 \leq i < n \land S_n \geq S_i \right}$입니다. 단순하게 계산하면 $O(N^2)$이고, 좌표 압축과 세그먼트 트리를 이용해 계산하면 $O(N \log N)$ 시간에 점화식을 계산할 수 있습니다.

세그먼트 트리에서 해야 하는 연산이 prefix maximum query임을 관찰하면 세그먼트 트리 대신 펜윅 트리를 사용할 수도 있습니다. 아래 코드는 펜윅 트리를 사용한 코드입니다.

전체 코드

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 <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int INF = 0xc0c0c0c0;

ll N, A[202020]; int D[202020], T[202020];
void Put(int x, int v){ for(x+=3; x<202020; x+=x&-x) T[x] = max(T[x], v); }
int Get(int x){ int r = INF; for(x+=3; x; x-=x&-x) r = max(r, T[x]); return r; }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i], A[i] += A[i-1];
    vector<ll> C(A, A+N+1);
    sort(C.begin(), C.end()); C.erase(unique(C.begin(), C.end()), C.end());
    for(int i=0; i<=N; i++) A[i] = lower_bound(C.begin(), C.end(), A[i]) - C.begin() + 1;
    memset(D, 0xc0, sizeof D);
    memset(T, 0xc0, sizeof T);
    D[0] = 0; Put(A[0], 0);
    for(int i=1; i<=N; i++){
        D[i] = D[i-1];
        if(int v = Get(A[i]) + i; v > 0) D[i] = max(D[i], v);
        if(D[i] >= 0) Put(A[i], D[i]-i);
    }
    cout << D[N];
}