hdoj 5087 Revenge of LIS II 【第二长单调递增子序列】

雨点打透心脏的1/2处 2022-08-13 14:50 66阅读 0赞

题目：[hdoj 5087 Revenge of LIS II ][hdoj 5087 Revenge of LIS II]

题意：很简单，给你一个序列，让你求第二长单调递增子序列。

分析：其实很简单，不知道比赛的时候为什么那么多了判掉了。

我们用O(n^2)的时间求单调递增子序列的时候，里面在加一层循环维护sum数组，表示前面有几个可以转移当当前，求前面sum的和保存到当前。

最后求最后一个sum【n-1】是否为1就ok，为1的话在最长的基础上减一，否则就是最长的。

AC代码：

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <math.h>
    #include <vector>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    const long long N =  1100;
    const long long Mod = 1000000007;
    typedef long long LL;
    int a[N],dp[N],sum[N];
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            int n;
            scanf("%d",&n);
            int ma = 0;
            for(int i=0;i<n;i++){
                scanf("%d",&a[i]);
                ma = max(a[i],ma);
            }
            a[n++] = ma+1;
            memset(sum,0,sizeof(sum));
            dp[0] = 1;sum[0] = 1;
            for(int i=1;i<n;i++)
            {
                int tmp = 0;
                for(int j=i-1;j>=0;j--)
                {
                    if(a[i]>a[j] && dp[j]>tmp)
                        tmp = dp[j];
                }
                for(int j=i-1;j>=0;j--)
                {
                    if(dp[j]==tmp && a[j]<a[i])
                        sum[i]+=sum[j];
                }
                if(sum[i]==0)
                    sum[i] = 1;
                dp[i] = tmp + 1;
            }
            int ans = 0;
            for(int i=0;i<n;i++)
                ans = max(ans,dp[i]);
            if(sum[n-1]==1)
                ans--;
            printf("%d\n",ans-1);
        }
        return 0;
    }

[hdoj 5087 Revenge of LIS II]: http://acm.hdu.edu.cn/showproblem.php?pid=5087