POJ3903(dp 최장 상승 하위 시퀀스 STL)

918 단어 pojdp
제목: 견본을 보면 알 수 있다.
사고방식: 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; }

좋은 웹페이지 즐겨찾기