9520번: NP-hard

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


$O(n^2)$

문제에 주어진 조건대로 탐사하려면 a1 > a2 > ... > ak-1 > ak < ak+1 <... < an-1 < an과 같이 방문해야 한다.
dp[i][j]: ...(결정) > i > ...(미결정) < j < ...(결정)과 같이 방문할 때 드는 시간의 최솟값

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 1500;
int n, w[MAX_N][MAX_N], dp[MAX_N][MAX_N];
int f(int x, int y) {
    if (y == n - 1 || dp[x][y]) return dp[x][y];
    return dp[x][y] = min(f(x, y + 1) + w[y][y + 1], f(y, y + 1) + w[x][y + 1]);
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) scanf("%d", &w[i][j]);
    printf("%d", f(0, 1) + w[0][1]);
    return 0;
}