HDU 3564 선분 트 리 + 단순 DP
제목: N 개 수 는 1 부터 N 까지 순서대로 N 개 위치 에 삽입 한 다음 에 하나씩 꽂 을 때마다 LIS 를 구한다.
사고방식: 한 번 씩 구 할 수 없다. 생각 을 바 꾸 려 면 먼저 모든 점 이 서열 에 있 는 위 치 를 구 한 다음 에 위 치 를 바탕 으로 LIS 를 구하 면 된다. 삽입 할 때 현재 삽 입 된 이 점 이 가장 크기 때문에 위 치 를 수치 로 삼 아 LIS 를 구 하 는 것 이 정확 하 다.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3fll;
const int maxn=100010;
int num[maxn],ans[maxn],numm[maxn],summ[maxn*4];
void slove(int n){
memset(ans,0,sizeof(ans));
int len=0;
ans[len++]=num[1];
printf("%d
",len);
for(int i=2;i<=n;i++){
int t=lower_bound(ans,ans+len,num[i])-ans;
if(ans[t]==0) ans[len++]=num[i];
else if(ans[t]>num[i]) ans[t]=num[i];
printf("%d
",len);
}
}
void buildtree(int le,int ri,int node){
summ[node]=ri-le+1;
if(le==ri) return ;
int t=(le+ri)>>1;
buildtree(le,t,node<<1);
buildtree(t+1,ri,node<<1|1);
}
int find1(int le,int ri,int node,int pos){
if(le==ri) return le;
int t=(le+ri)>>1;
if(summ[node<<1]<=pos) return find1(t+1,ri,node<<1|1,pos-summ[node<<1]);
else return find1(le,t,node<<1,pos);
}
void update(int pos,int le,int ri,int node){
summ[node]--;
if(le==ri) return ;
int t=(le+ri)>>1;
if(pos<=t) update(pos,le,t,node<<1);
else update(pos,t+1,ri,node<<1|1);
}
int main(){
int T,n,cas=1;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
buildtree(1,n,1);
for(int i=1;i<=n;i++) scanf("%d",&numm[i]);
for(int i=n;i>=1;i--){
int pos=find1(1,n,1,numm[i]+1);
num[i]=pos;
update(pos,1,n,1);
}
printf("Case #%d:
",cas++);
slove(n);
printf("
");
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
