[일기] 12.17

12.17

낙곡이 갑자기 노란 이름?

DP

1. 로곡P1020: 최장 불상승자 서열(LNIS)과 최장 불상승자 서열 개수.
먼저 LNIS:
소박\(O(n^2)\)방법: 뒤에서 앞으로 dp[i]=max(dp[i], dp[j]+1), i=a[j]를 만족시킨다.
빠르게\(O(n\log n)\) 방법: 이동한 후 매번 순서에서 그것보다 작은 첫 번째 수를 찾을 때마다 최적화를 업데이트합니다. 구체적인 원리는 다음과 같습니다.https://blog.csdn.net/wqtltm/article/details/81253935, 그림을 보는 것이 상당히 괜찮다.마찬가지로 이 수조들을 복용할 수 있음을 발견했기 때문에 d수조만 있으면 됩니다. 공간 복잡도 $O (n) $.
그 다음은 서열을 가장 적게 구분하는 개수다.
Dilworth의 정리가 있는데, 간단하게 말하면, 최소 상승하지 않는 서열의 개수 = 최장 상승하는 서열의 길이 (빼지 않고 개수를 길이로 바꾸는 것) 이다.사실 감성은 이해할 수 있다.
그럼 LIS 하나만 더 뛰면 돼.
주의: 첫 번째 그보다 작은 수를 찾으면 upperbound(a+1,a+n+1,x,greater())로 하지 말고lowerbound () +1, 냄비가 잘 나온다.보다 작으면 같은 이치다.

#include
using namespace std;
const int M=1e5+20;
int cnt,a[M];
struct LNIS{
    int dp[M],n;
    void init(){n=cnt;}
    void run(){
        int ans=0;
        for(int i=n;i>=1;--i){
            dp[i]=1;
            for(int j=n;j>=i+1;--j)
                if (a[i]>=a[j])
                    dp[i]=max(dp[i],dp[j]+1);
            ans=max(ans,dp[i]);
        }
        printf("%d
",ans);
    }
}L1;
struct LIS{
    int dp[M],n;
    void init(){n=cnt;}
    void run(){
        int ans=0;
        for(int i=1;i<=n;++i){
            dp[i]=1;
            for(int j=1;j<=i-1;++j)
                if (a[i]>a[j])
                    dp[i]=max(dp[i],dp[j]+1);
            ans=max(ans,dp[i]);
        }
        printf("%d
",ans);
    }
}L2;
int main(){
    int c;
    while(~scanf("%d",&c))
        a[++cnt]=c;
    L1.init();
    L2.init();
    L1.run();
    L2.run();
    return 0;
}

nlogn 방법:

#include
using namespace std;
const int M=1e5+20;
int cnt,a[M];
struct LNIS{
    int dp[M],d[M],n;
    void init(){n=cnt;}
    void run(){
        int len=1;
        for(int i=1;i<=n;++i){
            int p=upper_bound(d+1,d+len+1,a[i],greater())-d;//       a[i]   
            dp[i]=p,d[p]=a[i];
            if (p>len)
                len=p;
        }
        int ans=0;
        for(int i=1;i<=n;++i)
            ans=max(ans,dp[i]);
        printf("%d
",ans);
    }
}L1;
struct LIS{
    int dp[M],d[M],n;
    void init(){n=cnt;}
    void run(){
        int len=0;
        for(int i=1;i<=n;++i){
            int p=lower_bound(d+1,d+len+1,a[i])-d;//         a[i]   
            dp[i]=p,d[p]=a[i];
            if (p>len)
                len=p;
        }
        int ans=0;
        for(int i=1;i<=n;++i)
            ans=max(ans,dp[i]);
        printf("%d
",ans);
    }
}L2;
int main(){
    int c;
    while(~scanf("%d",&c))
        a[++cnt]=c;
    L1.init();
    L2.init();
    L1.run();
    L2.run();
    return 0;
}