POJ 2533 Longest Ordered Subsequence - from lanshui_Yang
3358 단어 sequence
제목 대의: 수열의 가장 긴 상승자 서열(엄격히 상승)을 구한다.
문제 해결 방법:
방법1: O (n^2)
dp[i]: i번째 위치로 처리되고 서열의 최장 상승 서열의 끝은 i의 길이임을 나타낸다.a[] 배열 저장 원 시퀀스
dp[i] = max{dp[j]+1},a[i]>a[j],0≤j≤i
방법2: O (nlogn)
복잡도가 낮아진 것은 사실 이 알고리즘에서 이분 검색을 사용했기 때문이다.원래 N개수는 O(n)로 처리해야 하는데 매번 N번을 찾아야 하는지 O(n)를 찾아야 하는지 모두 O(n^2)이다.현재 검색은 O(logn)의 2분 검색으로 바뀌었고 전체 복잡도는 O(nlogn)로 바뀌었다.
이 알고리즘의 구체적인 조작은 다음과 같다.
창고를 열면 창고 맨 위에 있는 원소 top와 읽은 원소temp를 비교하고temp>top는temp를 창고에 넣습니다.만약 temp < top 이라면, 창고에서 temp보다 큰 첫 번째 수를 2분 동안 찾고,temp로 대체합니다.최대 시퀀스 길이가 스택 크기 top입니다.
이치: 수열 중의 a[i]와 a[j], i
창고는 1, 5, 8이고 이때 3까지 읽고 3으로 5를 대체하여 1, 3, 8을 얻는다.6을 읽고 8을 6으로 바꿔 1, 3, 6을 얻는다.7을 더 읽고 최종 창고는 1, 3, 6, 7입니다.최대 증가 하위 시퀀스는 길이 4입니다.
코드를 보십시오.
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std ;
const int MAXN = 1e3 + 5 ;
int s[MAXN] ;
int dp[MAXN] ;
int n ;
int stap[MAXN] ;
int top ;
void init()
{
int i , j ;
for(i = 1 ; i <= n ; i ++)
{
scanf("%d" , &s[i]) ;
}
}
void solve() // O(n^2)
{
int i , j ;
dp[1] = 1 ;
for(i = 2 ; i <= n ; i ++)
{
dp[i] = 1 ;
for(j = 1 ; j < i ; j ++)
{
if(s[i] > s[j] && dp[i] < dp[j] + 1)
{
dp[i] = dp[j] + 1 ;
}
}
}
int MAX = -1 ;
for(i = 1 ; i <= n ; i ++)
{
if(MAX < dp[i])
MAX = dp[i] ;
}
printf("%d
" , MAX) ;
}
void solve2() // O(n log n)
{
top = 0 ;
stap[++ top] = s[1] ;
int i ;
for(i = 2 ; i <= n ; i ++)
{
if(s[i] > stap[top])
{
stap[++ top] = s[i] ;
}
else if(s[i] < stap[top])
{
int left , right , mid ;
left = 1 ;
right = top ;
while (left < right)
{
mid = (left + right) / 2 ;
if(stap[mid] < s[i])
{
left = mid + 1 ;
}
else if(stap[mid] == s[i])
{
break ;
}
else
{
right = mid ; // mid - 1 ！！
}
}
mid = (left + right) / 2 ;
stap[mid] = s[i] ;
}
}
printf("%d
" , top) ;
}
int main()
{
while (scanf("%d" , &n) != EOF)
{
init() ;
//solve() ;
solve2() ;
}
return 0 ;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2442 SequenceSequence Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 6120 Accepted: 1897 Description Given m sequences, e...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
