首页 > 代码库 > hdu 5087 Revenge of LIS II (DP)
hdu 5087 Revenge of LIS II (DP)
题意：
N个数，求第二长上升子序列的长度。
数据范围：
1. 1 <= T <= 100
2. 2 <= N <= 1000
3. 1 <= Ai <= 1 000 000 000
思路：
数据给的很暧昧，用n^2的算法可以过。故用n^2算法。只要在DP过程中记录得到f[i]是否只有一种方法即可。详看代码。
代码：
int T,n;int a[1005],f[1005];bool NOTalone[1005];int main(){ //freopen("test.in","r", stdin); cin>>T; while(T--){ scanf("%d",&n); rep(i,1,n) scanf("%d",&a[i]); rep(i,1,n) f[i]=1; mem(NOTalone,false); rep(i,2,n){ rep(j,1,i-1) if(a[i]>a[j]){ if(f[j]+1>f[i]){ f[i]=f[j]+1; NOTalone[i] = NOTalone[j]; } else if(f[j]+1==f[i]){ NOTalone[i]=true; } } } int t=f[1]; rep(i,2,n) t=max(t,f[i]); bool NOT_ALONE=false; int c=0; rep(i,1,n) if(t==f[i]) ++c,NOT_ALONE|=NOTalone[i]; if(c>1) NOT_ALONE=true; if(!NOT_ALONE) cout<<t-1<<endl; else cout<<t<<endl; } //fclose(stdin);}
hdu 5087 Revenge of LIS II (DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。