首页 > 代码库 > hdoj 5087 Revenge of LIS II 【第二长单调递增子序列】
hdoj 5087 Revenge of LIS II 【第二长单调递增子序列】
题目:hdoj 5087 Revenge of LIS II
题意:很简单,给你一个序列,让你求第二长单调递增子序列。
分析:其实很简单,不知道比赛的时候为什么那么多了判掉了。
我们用O(n^2)的时间求单调递增子序列的时候,里面在加一层循环维护sum数组,表示前面有几个可以转移当当前,求前面sum的和保存到当前。
最后求最后一个sum【n-1】是否为1就ok,为1的话在最长的基础上减一,否则就是最长的。
AC代码:
#include <iostream> #include <algorithm> #include <string> #include <math.h> #include <vector> #include <cstring> #include <cstdio> using namespace std; const long long N = 1100; const long long Mod = 1000000007; typedef long long LL; int a[N],dp[N],sum[N]; int main() { int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); int ma = 0; for(int i=0;i<n;i++){ scanf("%d",&a[i]); ma = max(a[i],ma); } a[n++] = ma+1; memset(sum,0,sizeof(sum)); dp[0] = 1;sum[0] = 1; for(int i=1;i<n;i++) { int tmp = 0; for(int j=i-1;j>=0;j--) { if(a[i]>a[j] && dp[j]>tmp) tmp = dp[j]; } for(int j=i-1;j>=0;j--) { if(dp[j]==tmp && a[j]<a[i]) sum[i]+=sum[j]; } if(sum[i]==0) sum[i] = 1; dp[i] = tmp + 1; } int ans = 0; for(int i=0;i<n;i++) ans = max(ans,dp[i]); if(sum[n-1]==1) ans--; printf("%d\n",ans-1); } return 0; }
hdoj 5087 Revenge of LIS II 【第二长单调递增子序列】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。