LIS의 또 다른 간단한 방법 nlogn (경로 포함)
엄격히 단조로이 점차 증가하다.
첫 번째 방법은 이산화+나무상수조/선단수조인데, 이런 방법은 나무상수조를 배운 사람은 모두 이해할 수 있다.
두 번째는 2점 + dp입니다.상수가 작아지면 시간과 공간이 앞의 것보다 조금 빠르다.
dp[i]=j를 정의하여 길이가 i인 상승 서열의 최소 말단 요소가 j임을 나타낸다.
다음은 코드를 제시하고 상세하게 설명하지 않겠습니다.
#include
#include
#include
#include
using namespace std;
const int maxn=1e5+7;
int p[maxn];
int n;
int dp[maxn];
int who[maxn];
int pre[maxn];
vectorpath;
int main()
{
scanf("%d",&n);
for(int i=0;i=0;i--)
printf("%d ",path[i]);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JavaScript에서 배열을 복제하는 6가지 방법 📑JavaScript에서 배열이란 무엇입니까? JavaScript에서 배열은 다른 요소를 저장하는 데 사용되는 단일 변수입니다. 값 목록을 저장하고 단일 변수로 액세스하려는 경우에 자주 사용됩니다. 경우에 따라 복사본...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
