hdu 5087 Revenge of LIS II

http://acm.hdu.edu.cn/showproblem.php?pid=5087

题意求第二长的上升序列。在求最长上升序列的同时加上一个数组，来记录以i为结尾的有多少条序列。如果n+1为结尾有多条，就输出dp[n+1]-1;

否则在这个最长的序列上每一个节点是不是都是num[i]==1，如果是，就输出dp[n+1]-2;否则输出dp[n+1]-1；

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 1005
 5 #define LL int
 6 using namespace std;
 7 
 8 int t;
 9 LL a[maxn];
10 int n;
11 int dp[maxn];
12 int num[maxn];
13 
14 int main()
15 {
16     scanf("%d",&t);
17     while(t--)
18     {
19         scanf("%d",&n);
20         memset(dp,0,sizeof(dp));
21         memset(num,0,sizeof(num));
22         for(int i=1; i<=n; i++)
23         {
24             scanf("%d",&a[i]);
25         }
26         a[n+1]=1000000001;
27         for(int i=1; i<=n+1; i++)
28         {
29             dp[i]=1;
30             num[i]=1;
31             for(int j=1; j<i; j++)
32             {
33                 if(a[j]<a[i]&&dp[i]<dp[j]+1)
34                 {
35                     num[i]=1;
36                     dp[i]=dp[j]+1;
37                 }
38                 else if(a[j]<a[i]&&dp[i]==dp[j]+1)
39                 {
40                     num[i]++;
41                 }
42             }
43         }
44         if(num[n+1]>1) printf("%d
",dp[n+1]-1);
45         else
46         {
47             int pos=n+1,j;
48             while(pos>0&&num[pos]==1)
49             {
50                 for(j=pos-1; j>=1; j--)
51                 {
52                     if(dp[j]+1==dp[pos]&&a[j]<a[pos]) break;
53                 }
54                 pos=j;
55             }
56             if(pos==0) printf("%d
",dp[n+1]-2);
57             else printf("%d
",dp[n+1]-1);
58         }
59     }
60     return 0;
61 }

View Code