동적 계획: 최 장 상승 서브 시퀀스 (LIS)

제목: 많은 공 설명
어느 날, 제 이 슨 은 작은 공 을 많이 샀 다.n 개 만큼 있다.그 는 숙제 를 다 한 후에 이 공 들 에 멍 하 게 있 었 다. 이때 옆집 어린이 ion 이 돌 아 왔 다.
제 이 슨 은 심심 할 때 게임 이 생각 났 다.그 는 이 n 개의 작은 공 을 1 에서 n 까지 표시 했다.그리고 순 서 를 어 지 럽 히 고 일렬 로 서 세 요.그리고 ion 에 게 조작 을 하 게 합 니 다.
매번 공 을 임의로 선택 하여 대열 의 맨 앞 이나 대열 의 맨 끝 에 놓 을 수 있다.적어도 몇 번 은 조작 을 해 야 공의 순 서 를 정렬 1, 2, 3, 4, 5... n 으로 바 꿀 수 있 느 냐 고 물 었 다.
입력 형식
여러 그룹의 테스트 데 이 터 를 포함 하고 각 그룹의 데이터 첫 줄 에 n (1 < = n < = 100) 을 입력 하면 n 개의 공이 있 음 을 나타 낸다.두 번 째 줄 에는 n 개의 숫자 ai (1 < = ai < = n) 가 있 고 ai 두 줄 은 각각 다르다.
출력 형식
각 조 의 테스트 데이터 출력 은 한 줄 을 차지 하고 최소 의 조작 횟수 를 나타 내 며 작은 공 을 질서 있 게 만든다.
입력 샘플
4
3 2 1 4
2
2 1
출력 샘플
2
1
분석: n 개의 난 서 를 순서 로 바 꾸 고 이동 횟수 가 가장 적다 는 뜻 이다.마찬가지 로 최 장 상승 서브 서열 을 사 용 했 는데 여기 서 의 상승 은 연속 적 이 고 등차 적 이다. n 개의 공의 번호 가 1 ~ n 이기 때문에 우 리 는 매번 1 이 증가 하 는 최 장 서브 서열 을 찾 았 고 나머지 수 는 팀 머리 나 팀 꼬리 로 옮 기 면 된다.그럼 최소 이동 횟수 는 n - LIS.
최 장 상승 서브 시퀀스
우 리 는 모두 알 고 있다. 동태 계획 의 한 특징 은 바로 현재 해 가 이전 단계 에서 출시 될 수 있다 는 것 이다. 이 를 통 해 우리 가 요구 하 는 문 제 를 더욱 작은 하위 문제 로 간략화 하 는 것 이다.하위 문 제 는 같은 구 해 방식 을 가지 고 있 는데, 단지 규모 가 작 을 뿐이다.최 장 상승 서브 시퀀스 는 이 특성 에 부합된다.우 리 는 n 개의 수의 최 장 상승 서브 서열 을 요구 합 니 다. 앞의 n - 1 개의 최 장 상승 서브 서열 을 구 한 다음 에 n 개의 수 와 판단 할 수 있 습 니 다.앞의 n - 1 개 수의 최 장 상승 서브 시퀀스 를 구하 면 앞의 n - 2 개 수의 최 장 상승 서브 시퀀스 를 구 할 수 있 습 니 다...................................................................
예 를 들 어 27, 1, 5, 6, 4, 3, 89 의 최 장 상승 서브 시퀀스 를 구 합 시다.우 리 는 d (i) (i 8712 ° [1, n]) 를 정의 하여 앞의 i 개 수 는 A [i] 로 끝 나 는 가장 긴 상승 서브 시퀀스 의 길 이 를 나타 낸다.
앞의 1 개 수 d (1) = 1 자 서열 은 2 이다.
앞의 2 개 수 7 앞 에 2 가 7 d (2) 보다 작 음 = d (1) + 1 = 2 자 서열 은 27 이다.
앞의 3 개 수 는 1 앞에서 1 보다 작은 것 이 없고 1 자체 구성 길이 가 1 인 하위 서열 d (3) = 1 하위 서열 은 1 이다.
앞의 4 개 수 5 앞 에는 2 보다 작은 5 d (4) = d (1) + 1 = 2 자 서열 이 25 이다.
앞의 5 개 수 6 앞 에 25 가 6 d (5) 보다 작 음 = d (4) + 1 = 3 자 서열 은 25 6 이다.
앞의 6 개 수 4 앞 에 2 가 4 d (6) 보다 작 음 = d (1) + 1 = 2 자 서열 은 24 이다.
앞의 7 개 수 3 앞 에 2 가 3 d (3) 보다 작 음 = d (1) + 1 = 2 자 서열 은 23 이다.
앞의 8 개 수 8 앞 에는 2, 5, 6 이 8 d (8) 보다 작 음 = d (5) + 1 = 4 자 서열 이 2, 5, 6, 8 이다.
앞의 9 개 수 9 앞 에 2, 5, 6, 8 이 9 d (9) 보다 작 음 = d (8) + 1 = 5 자 서열 은 2, 5, 6, 8 9 이다.
d (i) = max {d (1), d (2),..., d (i)} 우 리 는 이 9 개의 수의 LIS 가 d (9) = 5 라 는 것 을 알 수 있다.
요약 하면 d (i) 는 A [i] 로 끝 나 는 것 을 찾 는 것 이다. A [i] 이전의 최 장 상승 서브 시퀀스 + 1. A [i] 이전에 A [i] 보다 작은 숫자 가 없 었 을 때 d (i) = 1.모든 d (i) 에서 가장 큰 것 은 가장 긴 상승 서브 시퀀스 이다.다음은 코드 구현 알고리즘 입 니 다.

int LIS(int A[],int n)
{
    int* d = new int[n];
    int len = 1;
    int i,j;
    for(i=0;i=d[i])
                d[i]=d[j]+1;
        }
        if(d[i]>len) len=d[i];
    }
    delete []d;
    return len;
}

이 문제 코드 구현:

#include
using namespace std;
const int maxn = 101;
int LIS(int A[],int n)
{
	int* d = new int[n];
	int len = 1;
	for(int i=0;id[i])
			{
				d[i]=d[j]+1;
			}
		}
		if(d[i]>len) len = d[i];
	}
	return len;
}
int main()
{
	int n;
	int a[maxn];
	scanf("%d",&n);
	for(int i = 0;i