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 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
배열 참조... 그리고 하지 않는 방법!이 코드를 보세요... breeds 배열에 무슨 일이 일어날 것 같나요? 그래서... 우리는 품종 배열이 아닌 강아지 배열을 변경하고 싶었습니다. 우리는 JavaScipt에 다음과 같이 말했습니다. 새 어레이를 원합...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
