oVeron

\(i\)번째 병사들까지의 전투력의 최댓값을 구했다면, 이 정보를 이용해 \(i+1\)번째 병사들까지의 전투력의 최댓값을 구할 수 있다. 이 문제는 DP 문제로, 우선 점화식을 만들어 보자. \(dp[i] = max(dp[j] + f(s[i] - s[j]))\) (단, \(i > j\), \(s[i]\) : \(i\)번째 병사들까지의 전투력의 합,\(f(x) = ax^2+bx+c\)) 이 점화식을 \(j\)에 대해 정리해 보자. \(dp[i] = max(dp[j] + f(s[i] - s[j]))\) \(dp[i] = max(dp[j] + a(s[i])^2 - 2as[i]s[j] + a(s[j])^2 + bs[i] + bs[j] + c)\)  이때, \(i\)는 \(max\)와 관련이 없으므로 바깥으로 정..

알고리즘/baekjoon 2024. 7. 13. 19:39