풀이
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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이