K번 도시를 방문하기 위해서는 K보다 작은 도시를 모두 방문하고 방문하거나
K번도시를 방문한 후에 K보다 작은도시를 모두 방문하면 된다.
K번도시보다 작은도시를 K번도시 이전에 방문하고 다른하나는 K번도시방문후에 방문하면 안된다.
이때 모든 도시를 방문하기위해 드는 시간의 최솟값을 구하는 문제다.
문제 이해를 계속 못했다.
문제의 핵심은 $v_{1}>v_{2}>...>v_{k}<v_{k+1}<...<v_{n}$의 수열중 최솟값을 구하는 문제가 된다.
(위와같은 수열을 bitonic sequence라 한다.)
즉, 4개의 도시중에 만약 방문순서를 2,1,3을 했다면 4는 왼쪽 또는 오른쪽에 붙일 수 있다.
(4,2,1,3 또는 2,1,3,4)
위의 로직을 catch했다면 경찰차문제 풀듯이 쉽게 dp로 풀 수 있다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 987654321
int N;
int adj[1501][1501];
int dp[1501][1501];
int solve(int l, int r) {
if (l == N - 1 || r == N - 1) return 0;
int &ret = dp[l][r];
if (ret != -1) return ret;
ret = INF;
int next = max(l, r) + 1;
return ret = min(ret, min(solve(next, r) + adj[next][l], solve(l, next) + adj[r][next]));
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d", &N);
for (int n = 0;n < N;n++) for (int m = 0;m < N;m++) scanf("%d", &adj[n][m]);
printf("%d\n", solve(0, 1) + adj[0][1]);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기