首页 > 代码库 > hdu5087 Revenge of LIS II (dp)
hdu5087 Revenge of LIS II (dp)
只要理解了LIS，这道题稍微搞一下就行了。
求LIS（最长上升子序列）有两种方法：
1.O(n^2)的算法：设dp[i]为以a[i]结尾的最长上升子序列的长度。dp[i]最少也得是1，就初始化为1，则dp[i]=max(dp[i],dp[j]+1)（其中j<i且a[j]<a[i]）。
int gao(){ int ans=0; for(int i=0;i<n;i++) { dp[i]=1; for(int j=0;j<i;j++) { if(a[j]<a[i]) { dp[i]=max(dp[i],dp[j]+1); } } ans=max(ans,dp[i]); } return ans;}
2.O(n*lgn)算法：有这样一个性质：如果上升子序列长度相同，那么最末尾最小的那种在之后的比较中最有优势（有点贪心的味道）。根据这个，设dp[i]为长度为i+1的上升子序列中末尾元素的最小值。开始dp全初始化为INF，每次更新时前面的dp都是排好序的，所以就可以二分来找。
int gao(){ fill(dp,dp+n,INF); for(int i=0;i<n;i++) { *lower_bound(dp,dp+n,a[i])=a[i]; } ans=lower_bound(dp,dp+n,INF)-dp;}
对于本题，要求输出第二长子序列的长度。那么就找LIS，如果LIS只有一种情况可以得到，那么输出LIS-1，否则输出LIS。
用num数组来记录能达到当前长度的方法数。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=1000+10;const LL mod=1000000007;int T,n,a[maxn],dp[maxn],num[maxn];int main(){ //freopen("in8.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&T); while(T--) { scanf("%d",&n); int ans=0; for(int i=0; i<n; i++) { scanf("%d",&a[i]); } for(int i=0; i<n; i++) { dp[i]=1; num[i]=1; for(int j=0; j<i; j++) { if(a[j]<a[i]) { if(dp[j]+1>dp[i]) { num[i]=num[j]; dp[i]=dp[j]+1; } else if(dp[j]+1==dp[i]) { num[i]+=num[j]; } } } if(dp[i]>ans) { ans=dp[i]; } } int num1=0; for(int i=0;i<n;i++) { if(dp[i]==ans) { num1+=num[i]; } } if(num1==1) { printf("%d\n",ans-1); } else { printf("%d\n",ans); } } //fclose(stdin); //fclose(stdout); return 0;}
hdu5087 Revenge of LIS II (dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。