首页 > 代码库 > hdu 5087 Revenge of LIS II

hdu 5087 Revenge of LIS II

2024-07-30 16:10:21   222人阅读

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\n",dp[n+1]-1);45         else46         {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\n",dp[n+1]-2);57             else printf("%d\n",dp[n+1]-1);58         }59     }60     return 0;61 }
View Code

 

hdu 5087 Revenge of LIS II


联系
我们