백준 1823 - 수확 (C++)

문제 문제 링크 BOJ 1823 - 수확 문제 요약 $N$개의 벼와 그 가치가 주어진다. 문제에 정의된 규칙대로 벼를 수확할 때 얻을 수 있는 최대 이익을 구해보자.

제한 TL : $1$ sec, ML : $128$ MB $1 ≤ N ≤ 2,000$ $1 ≤ N_i ≤ 1,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 결국 양 끝 점에서만 상태가 변화 한다는 것에 주목하면 이미 문제를 푼 것이나 다름 없다. 다음과 같이 점화식을 정의하자.

$dp[p][q]$ : 현재 구간 $[p, q]$를 보고 있을 때 얻을 수 있는 최대 이익. 만약 왼 쪽 점을 취한다면 $a[p] * (n - (q - p))$ 의 이득이 발생하고, 오른 쪽 점을 취한다면 $a[q] * (n - (q - p))$ 의 이득이 발.....