Revenge of LIS II

3
2
1 1
4
1 2 3 4
5
1 1 2 2 2

1
3
2
Hint
For the first sequence, there are two increasing subsequence: [1], [1]. So the length of the second longest increasing subsequence is also 1, same with the length of LIS.
 

题目大意：求一个序列的所有递增子序列中第二长的那个递增子序列的长度。

解题思路：根据dp求解一个序列的最大递增子序列的模板，dp[i]表示以第i个数结尾的最长上升子序列的长度 ，c[i]表示到达dp[i]的方法数，比如序列1 2 2 3 2；dp[2]=2，c[2]=1；dp[3]=2，c[3]=1；dp[4]=3，c[4]=2。
最后查询最大递增子序列出现的次数，如果出现一次，就最大长度减一输出；如果出现不止一次，就输出最大长度。

代码如下：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <fstream>
#include <limits.h>
#define debug "output for debug\n"
#define pi (acos(-1.0))
#define eps (1e-6)
#define inf (1<<28)
#define sqr(x) (x) * (x)
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef unsigned long long ULL;
const int MAX=1005;
int a[MAX],c[MAX],dp[MAX];
int main()
{
    int i,j,n,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int ans=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            dp[i]=1,c[i]=1;
            for(j=1;j<i;j++)
            {
                if(a[i]>a[j]&&dp[i]<dp[j]+1)
                {
                    dp[i]=dp[j]+1;
                    c[i]=c[j];
                }
                else if(dp[i]==dp[j]+1)
                    c[i]=2;
            }
            ans=max(ans,dp[i]);
        }
        int num=0;
        for(i=1;i<=n;i++)
        {
            if(dp[i]==ans)
                num+=c[i];
        }
        if(num==1)
            printf("%d\n",ans-1);
        else
            printf("%d\n",ans);
    }
    return 0;
}

HDU 5087 Revenge of LIS II（次大递增子序列）

原文：http://blog.csdn.net/yanghuaqings/article/details/47726259