Uva 11456 - Trainsorting

Problem Link

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=651&problem=2451&mosmsg=Submission+received+with+ID+20661170

Description of Problem

  자동차의 행렬이 주어진다. 행렬에는 자동차의 무게가 저장된어 있다. 이때 자동차를 연결한다. 자동차를 연결하는 제약조건은 앞쪽 즉, 왼쪽의 자동차가 뒷쪽 즉, 오른쪽의 자동차보다 무거워야 된다. 이때 주어진 조건을 만족하는 가장 긴 자동차 행렬의 길이를 구하는 문제다.

Algorithm to Solve the Problem

  답은 제약조건을 만족하는 가장 긴 행렬의 길이이다. 하지만 이 길이를 구하기 위하여 실제로 연결되는 자동차들의 행렬을 생각해보자. 어떤 자동차를 정답 행렬에 추가하기로 결정했다. 이때 다음으로 일어날 수 있는 모든 경우는 다음과 같다.

1. 더 가벼운 자동차라면 해당 자동차 뒤에 붙인다.

2. 더 무거운 자동차라면 해당 자동차 앞에 붙인다.

3. 자동차를 붙이지 않는다.

여기까지 생각하고 보면 문제가 매우 단순해진다. 정답 행렬에 가장 먼저추가 되는 자동차는 결과적으로 정답행렬에 중간에 위치하게 된다.(대부분의 케이스에서) 즉, 가장 먼저 추가되는 자동차를 시작점으로 마지막 끝점까지의 최대 증가 부분 수열과 최대 감소 부분 수열의 합이 가장 큰 시작점을 찾는 다면 해당 시작점이 정답 수열의 가운대에 위치하며 해당 시작점 앞으로는 최대 감소 수열이 해당 시작점 뒤로는 최대 증가 수열이 위치하는 최적해를 구할 수 있는 것이다.

Analysis Time Complexity

  위 알고리즘의 시간복잡도는 

O(각 시작점당 lis와 lds를 구하는 시간 + 각 시작점당 lis와 lds의 합 비교)이다.

이를 자동차수의 최댓값은 2000 이므로 시간복잡도는 아래 이하이다.

O(2000 * 2000 + 2000) = O(4000000)

4000,000은 컴퓨터가 계산하기에 너무나도 여유로운 숫자이다.

Solution Code for This Problem

#include<cstdio>

#include<algorithm>

using namespace std;

int main() {

int cars[2002], lis[200], lds[200], cases, n;

scanf("%d", &cases);

while(cases--) {

scanf("%d", &n);

for(int i = 0; i < n; ++i) 

scanf("%d", &cars[i]);

//cars[i]를 시작점으로 하는 lis를 구하는 부분

for(int i = n - 1; i >= 0; --i) {

lis[i] = 1;

for(int j = i + 1; j < n; ++j) 

if(cars[i] < cars[j])

lis[i] = max(lis[j] + 1, lis[i]);

}

//cars[i]를 시작점으로 하는 lds를 구하는 부분

for(int i = n - 1; i >= 0; --i) {

lds[i] = 1;

for(int j = i + 1; j < n; ++j)

if(cars[i] > cars[j])

lds[i] = max(lds[j] + 1, lds[i]);

}

int ret = 0;

for(int i = 0; i < n; ++i) 

ret = max(ret, lis[i] + lds[i] - 1);

printf("%d\n", ret);

}

}