hdu5087 Revenge of LIS II (dp)

只要理解了LIS，这道题稍微搞一下就行了。

求LIS（最长上升子序列）有两种方法：

1.O(n^2)的算法：设dp[i]为以a[i]结尾的最长上升子序列的长度。dp[i]最少也得是1，就初始化为1，则dp[i]=max(dp[i],dp[j]+1)（其中j<i且a[j]<a[i]）。

int gao()

{

    int ans=;

    for(int i=;i<n;i++)

    {

        dp[i]=;

        for(int j=;j<i;j++)

        {

            if(a[j]<a[i])

            {

                dp[i]=max(dp[i],dp[j]+);

            }

        }

        ans=max(ans,dp[i]);

    }

    return ans;

}

O(n^2)

2.O(n*lgn)算法：有这样一个性质：如果上升子序列长度相同，那么最末尾最小的那种在之后的比较中最有优势（有点贪心的味道）。根据这个，设dp[i]为长度为i+1的上升子序列中末尾元素的最小值。开始dp全初始化为INF，每次更新时前面的dp都是排好序的，所以就可以二分来找。

int gao()

{

    fill(dp,dp+n,INF);

    for(int i=;i<n;i++)

    {

        *lower_bound(dp,dp+n,a[i])=a[i];

    }

    ans=lower_bound(dp,dp+n,INF)-dp;

}

O(n*lgn)

对于本题，要求输出第二长子序列的长度。那么就找LIS，如果LIS只有一种情况可以得到，那么输出LIS-1，否则输出LIS。

用num数组来记录能达到当前长度的方法数。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<cmath>

#include<map>

#include<set>

#include<vector>

#include<algorithm>

#include<stack>

#include<queue>

#include<cctype>

#include<sstream>

using namespace std;

#define pii pair<int,int>

#define LL long long int

const int eps=1e-;

const int INF=;

const int maxn=+;

const LL mod=;

int T,n,a[maxn],dp[maxn],num[maxn];

int main()

{

    //freopen("in8.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        int ans=;

        for(int i=; i<n; i++)

        {

            scanf("%d",&a[i]);

        }

        for(int i=; i<n; i++)

        {

            dp[i]=;

            num[i]=;

            for(int j=; j<i; j++)

            {

                if(a[j]<a[i])

                {

                    if(dp[j]+>dp[i])

                    {

                        num[i]=num[j];

                        dp[i]=dp[j]+;

                    }

                    else if(dp[j]+==dp[i])

                    {

                        num[i]+=num[j];

                    }

                }

            }

            if(dp[i]>ans)

            {

                ans=dp[i];

            }

        }

        int num1=;

        for(int i=;i<n;i++)

        {

            if(dp[i]==ans)

            {

                num1+=num[i];

            }

        }

        if(num1==)

        {

            printf("%d\n",ans-);

        }

        else

        {

            printf("%d\n",ans);

        }

    }

    //fclose(stdin);

    //fclose(stdout);

    return ;

}

巴特西

hdu5087 Revenge of LIS II (dp)

最新文章

热门文章