首页 > 代码库 > hdu 5087 Revenge of LIS II
hdu 5087 Revenge of LIS II
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 }
hdu 5087 Revenge of LIS II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。