15560 : 구간 합 최대? 1

풀이

max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i))

= max(U * (K[i] + K[i+1] + ... K[j]) + V * (j - i + 1)) - V

모든 A[i]U * A[i] + V로 바꿔주면

max(A[i] + ... + A[j])가 최대가 되는 연속 구간 최대 합을 구하는 문제가 된다.

15561번 풀이에 세그트리를 이용한 구현이 있다.

여긴 나이브한 구현.

코드

#include <cstdio>
int max(int a, int b) { return a > b ? a : b; }
int n, q, u, v, a[1001];
int main() {
    scanf("%d %d %d %d", &n, &q, &u, &v);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i] = u * a[i] + v;
    }
    while (q--) {
        int c, x, y;
        scanf("%d %d %d", &c, &x, &y);
        if (!c) {
            int res = -1e9, sum = -1e9;
            for (int i = x; i <= y; i++) res = max(res, sum = max(sum, 0) + a[i]);
            printf("%d\n", res - v);
        }
        else a[x] = u * y + v;
    }
    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-04-12 18:20

Read more posts by this author