POJ3903(dp 최장 상승 하위 시퀀스 STL)
사고방식: dp[i]의 상태는 길이가 i+1인 상승자 서열 중 가장 작은 값이다.
여기에 STL lower를 사용했습니다bound 헤더 파일은 "algorithm", 함수 lowerbound () 는first와last의 전폐후 개방 구간에서 2분 검색을 하고 val보다 크거나 같은 첫 번째 요소의 위치를 되돌려줍니다.모든 요소가 val보다 작으면 last의 위치로 돌아갑니다
#include
#include
#include
#include
using namespace std;
#define inf 0x3f3f3f3f
int dp[100010];
int a[100010];
int main()
{
//freopen("in.txt","r",stdin);
int n;
while(scanf("%d",&n) != EOF){
memset(dp,inf,sizeof(dp));
for(int i = 0;i < n; i++){
scanf("%d",&a[i]);
}
for(int i = 0;i < n; i++){
*lower_bound(dp,dp+n,a[i]) = a[i]; // a[i]
}
printf("%d
",lower_bound(dp,dp+n,inf)-dp); //
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
