BOJ 2313 보석 구매하기

BOJ 2313 보석 구매하기

[분류 : 다이나믹 프로그래밍]

 

연속 부분 수열의 합을 최대로 하는 방식을 여러 차례 반복해서 진행하면 되는 문제.

[주의해야 할 점]

1. 정답은 32비트 int 자료형에 들어가지 않을 수 있다. 오버플로우에 유의하자. 
2. 구간의 길이가 짧아야한다. 0인 요소에 대해 처리할 필요가 있다. 가령 "0 0 0 1 0"이 입력으로 들어오면 [1, 4]가 아니라 [4, 4]가 정답 구간이다. 

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int n, L, sum, asum, i, l, r, d, al, ar;
    long long ans = 0;
    vector<pair<int, int>> seg;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &L);
        asum = sum = -1e9;
        al = ar = l = r = 0;
        for (i = 0; i < L; i++) {
            scanf("%d", &d);

            if (sum < 0) {
                sum = d;
                l = r = i;
            }
            else {
                if(sum) r++;
                else l = r = i;
                sum += d;
            }
            if (asum < sum || (asum == sum && r - l < ar - al)) {
                asum = sum;
                al = l, ar = r;
            }
        }
        seg.push_back({ al, ar });
        ans += asum;
    }
    printf("%lld\n", ans);
    for (auto& u : seg)
        printf("%d %d\n", u.first + 1, u.second + 1);
    return 0;
}