首页 > 代码库 > hdu 5087 Revenge of LIS II dp
hdu 5087 Revenge of LIS II dp
传送门:hdu 5087
总结起来题目意思就是给定一个长度为n的数组,找出次长的最长递增子序列的长度(次长与最长允许相等)
这里n的范围只到1000,因此O(n^2)的算法也可过,比赛时候卡了好久在想O(nlogn)的....(>.<)
用dp[i]记录以位置i为末尾时的最大长度,dp2[i]记录以位置i为末尾的次大长度,dp求出所有i的dp[i]与dp2[i],并在同时更新最大长度与次大长度,最后直接输出次大长度即可。
/****************************************************** * File Name: 5087.cpp * Author: kojimai * Create Time: 2014年11月01日 星期六 22时41分42秒 ******************************************************/ #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> using namespace std; #define FFF 1005 int a[FFF],dp[FFF],dp2[FFF]; int getans(int i,int j)//以j为末尾的递增子序列的最大长度更新新长度 { if(a[i] < a[j]) return 0; else if(a[i] == a[j])//相等时构成长度相同 return dp[j]; else//比a[j]大时构成的新长度+1 return dp[j] + 1; } int getans2(int i,int j)//以j为末尾的递增子序列的次大长度更新新长度 { if(a[i] < a[j]) return 0; else if(a[i] == a[j]) return dp2[j]; else return dp2[j] + 1; } int main() { int keng; scanf("%d",&keng); while(keng--) { int n; scanf("%d",&n); for(int i = 0;i < n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof(dp)); memset(dp2,0,sizeof(dp2)); dp[0] = 1; int one = 1,second = 0;//one当前求得的最大长度,second为次大长度 for(int i = 1;i < n;i++) { dp[i] = 1; //cout<<" i = "<<i<<endl; for(int j = 0;j < i;j++) { int tmp = getans(i,j); // cout<<" tmp1 = "<<tmp; if(tmp > dp[i]) { dp2[i] = dp[i]; dp[i] = tmp; } else if(tmp > dp2[i]) dp2[i] = tmp; tmp = getans2(i,j); // cout<<" tmp2 = "<<tmp<<endl; if(tmp > dp2[i]) dp2[i] = tmp; } //cout<<" dp = "<<dp[i]<<" "<<dp2[i]<<endl; if(one < dp[i]) { second = one; one = dp[i]; } else if(second < dp[i]) { second = dp[i]; } if(second < dp2[i]) second = dp2[i]; } cout<<second<<endl; } return 0; }
hdu 5087 Revenge of LIS II dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。