백준9520 NP-Hard

작성일 | In

문제 링크

  • http://icpc.me/9520

문제 출처

  • 2013/2014 COCI #2 4번

사용 알고리즘

  • DP

시간복잡도

  • $O(N^2)$

풀이

최적해는 감소하다가 1을 찍고 증가하는 형태입니다.
1부터 시작해서 정점을 양끝에 추가하는 형태의 DP를 해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

ll n, g[1515][1515];
ll dp[1515][1515];

ll f(int s, int e, int x){
    ll &res = dp[s][e];
    if(res != -1) return res;
    if(x > n) return res = 0;
    ll t1 = f(x, e, x+1) + g[x][s];
    ll t2 = f(s, x, x+1) + g[e][x];
    return res = min(t1, t2);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> g[i][j];
    memset(dp, -1, sizeof dp);
    cout << f(1, 1, 1);
}