首页 > 代码库 > hdu 5087 Revenge of LIS II ( LIS ,第二长子序列)

hdu 5087 Revenge of LIS II ( LIS ,第二长子序列)

2024-07-30 22:43:32   221人阅读

链接：hdu 5087

题意：求第二大的最长升序子序列

分析：这里的第二大指的是，所有的递增子序列的长度（包括相等的），

从大到小排序后，排在第二的长度

BestCoder Round #16 上的第二题，注意  1 1 2 这组数据，答案应为2

思路1.每次将最长的两个上升子序列长度记录，最后再排序，取第二大的即可

思路2.如果最长的上升子序列长度（ans）唯一，那第二大应为ans-1

否则，第二大的就为 ans


[cpp] view plaincopyprint?
  1. #include<stdio.h>  
  2. #include<algorithm>  
  3. using namespace std;  
  4. int a[1010],dp[1010][2],ans[2010],n;  
  5. int main()  
  6. {  
  7.     int T,i,j,k,x,y;  
  8.     scanf("%d",&T);  
  9.     while(T--){  
  10.         scanf("%d",&n);  
  11.         for(i=0;i<n;i++)  
  12.             scanf("%d",&a[i]);  
  13.         k=0;  
  14.         for(i=0;i<n;i++){  
  15.             dp[i][0]=1;  
  16.             dp[i][1]=0;  
  17.             for(j=0;j<i;j++){  
  18.                 if(a[j]<a[i]){  
  19.                     x=dp[j][0]+1;   
  20.                     y=dp[j][1]+1;  
  21.                     if(x>dp[i][0])   //更新最大的两个长度  
  22.                         swap(x,dp[i][0]);  
  23.                     if(x>y)  
  24.                         swap(x,y);  
  25.                     if(y>dp[i][1])  
  26.                         dp[i][1]=y;  
  27.                 }  
  28.             }  
  29.             ans[k++]=dp[i][0];  //将每次最大的两个值记录下来  
  30.             ans[k++]=dp[i][1];  
  31.         }  
  32.         sort(ans,ans+k);  
  33.         printf("%d\n",ans[k-2]); //输出排序后第二大的  
  34.     }  
  35.     return 0;  
  36. }  

[cpp] view plaincopyprint?
  1. #include<stdio.h>  
  2. #include<string.h>  
  3. #define max(a,b) a>b?a:b  
  4. int a[1010],dp[1010],num[1010],n;  
  5. int main()  
  6. {  
  7.     int T,i,j,cnt,ans;  
  8.     scanf("%d",&T);  
  9.     while(T--){  
  10.         scanf("%d",&n);  
  11.         for(i=0;i<n;i++)  
  12.             scanf("%d",&a[i]);  
  13.         ans=1;  
  14.         for(i=0;i<n;i++){  
  15.             num[i]=dp[i]=1;  
  16.             for(j=0;j<i;j++){  
  17.                 if(a[j]<a[i]&&dp[j]+1>dp[i]){  
  18.                     dp[i]=dp[j]+1;  
  19.                     num[i]=num[j];   //记录出现的次数  
  20.                 }  
  21.                 else if(a[j]<a[i]&&dp[j]+1==dp[i])  
  22.                     num[i]+=num[j];   //记录出现的次数  
  23.             }  
  24.             ans=max(ans,dp[i]); //记录最大值  
  25.         }  
  26.         cnt=0;  
  27.         for(i=0;i<n;i++)  
  28.             if(dp[i]==ans)  
  29.                 cnt+=num[i];  //计算最大值出现的总次数  
  30.         if(cnt==1)          //这里改成cnt>1输出ans,否则ans-1，wrong了，很郁闷  
  31.             printf("%d\n",ans-1);  
  32.         else  
  33.             printf("%d\n",ans);  
  34.     }  
  35.     return 0;  
  36. }  

hdu 5087 Revenge of LIS II ( LIS ,第二长子序列)


联系
我们