求助,只有40分。。。

P1439 【模板】最长公共子序列

xiaolou @ 2019-01-24 20:29:25

RT,WA6个点,求助。。。

#include <bits/stdc++.h>

using namespace std;
int dp[100005];
int a[100005];
int b[100005];
int m[100005];

int main()
{
    int n;
    int ans=0;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        m[a[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        cin >> b[i];
        dp[i]=0x3f3f3f3f;
    }
    for(int i=1;i<=n;i++)
    {
        if(m[b[i]]>dp[ans])
        {
            ans++;
            dp[ans]=m[b[i]];
        }
        else
        {   
            int l=0,r=100000;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(dp[mid]>m[b[i]])
                    r=mid-1;
                else
                    l=mid+1;
            }
            dp[l]=min(m[b[i]],dp[l]);
        }
    }
    cout << ans;
    return 0;
} 

by WAWA @ 2019-01-25 16:58:31

没二分


by supinrui @ 2019-01-25 16:59:15


|