11570번: 환상의 듀엣

https://www.acmicpc.net/problem/11570


$O(n^2)$

dp[x][y]: a[1...y]를 노래했고 a[x], a[y]가 두 사람이 부른 마지막 음일 때 힘든 정도의 최솟값

아래 소스에서는 위 dp정의와는 다르게 악보를 뒤에서부터 읽었다고 가정하였다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, dp[2000][2001], ck[2000][2000], a[2001];
int f(int x, int y) {
    if (y < n && !ck[x][y]) {
        ck[x][y] = 1;
        dp[x][y] = min(f(x, y + 1) + abs(a[y] - a[y + 1]), f(y, y + 1) + (x > 0)*abs(a[x] - a[y + 1]));
    }
    return dp[x][y];
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    printf("%d", f(0, 1));
    return 0;
}