최적화5 백준 15560 / C++ https://www.acmicpc.net/problem/15560 15560번: 구간 합 최대? 1 첫 번째 줄에 정수 N과 Q, U, V가 입력된다. (1 ≤ N, Q ≤ 103, - 5 ≤ U, V ≤ 5) 두 번째 줄에 정수 K1, K2, ..., KN이 주어진다. ( - 102 ≤ Ki ≤ 102) 세 번째 줄부터 쿼 www.acmicpc.net [ 풀이 ] 식을 정돈하자. 누적합 psum으로 정리하면.. U*(psum[j]-psum[i-1])+V(j-i)이다. 왠지 U*psum[i]+V*i 를 다시 f(i)로 놓고 싶다. 그러면 식은 f(j)-f(i-1)-V가 된다. 이제 문제는 구간 [A,B]에서 f(j)-f(i-1)의 최댓값을 구하면 된다. O(N)에 해결하자. dp[j]를 f(j)-f(i.. 2022. 8. 1. 이전 1 2 다음