최장 불하강 서브 시퀀스 설명
방법1(O(n^2):
dp의 방법을 쉽게 알 수 있습니다. f[i]를 설정하면 i로 끝나는 가장 긴 하위 서열의 길이를 표시하지 않습니다.
비교적 쉬우니 말하지 말자.
코드:
#include
#include
using namespace std;
int n,ans=0;
int a[1000],f[1000];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j 메서드 2(O (nlogn):
만약 n≥3000이 되면 카드를 끊기 어렵다.
그래서 f[i]를 설정하면 i로 끝나는 가장 작은 수가 얼마인지 나타낸다.
f수 그룹의 마지막 자리를 자리수로 설정합니다.
한 번 지나면 최종적인tail이 결과라는 것을 알 수 있다.
1. a[i]≥f[tail]이면 쉽게 알 수 있듯이 욕심을 부리며 f수조의 끝에 놓는다(최장 만족은 성질을 떨어뜨리지 않기 때문에 길이는 1).
2. 그렇지 않으면 우리는 경로를 기록하지 않아도 (그 수를 결과로 선택한 것을 기록함) f수조에서 a[i]보다 큰 가장 작은 수를 a[i]로 욕심을 부릴 수 있다고 생각한다.정확성이 뚜렷하다.최종 결과에 영향을 주지 않기 때문이다.그리고 나는 f수조에서 a[i]보다 큰 가장 작은 수를 a[i]로 바꾸었다. 이것은 의심할 여지없이 뒤에 대한 제한을 축소한 것이다.
견본을 주다
8
1 100 101 1 2 3 4 5
만약 2 조작을 하지 않으면 결과는 3(1100101)이다.분명히 우리는 6(1, 1, 2, 3, 4, 5)을 선택해야 한다. 바로 100101을 삭제하는 것이다.
알아볼 수 없어, 괜찮아, 천천히 해, 몇 번 더 읽어.
코드:
#include
#include
using namespace std;
int n,tail=1;
int a[100000],f[100000];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
f[1]=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]>=f[tail]) f[++tail]=a[i]; else
{
int p=lower_bound(f+1,f+tail+1,a[i])-f;
while(f[p]==a[i]&&p<=tail) p++;
f[p]=a[i];
}
}
printf("%d",tail);
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
