hdu 5087(次长上升子序列)
Revenge of LIS II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1427 Accepted Submission(s): 489
computer science, the longest increasing subsequence problem is to find
a subsequence of a given sequence in which the subsequence's elements
are in sorted order, lowest to highest, and in which the subsequence is
as long as possible. This subsequence is not necessarily contiguous, or
unique.
---Wikipedia
Today, LIS takes revenge on you, again.
You mission is not calculating the length of longest increasing
subsequence, but the length of the second longest increasing
subsequence.
Two subsequence is different if and only they have
different length, or have at least one different element index in the
same place. And second longest increasing subsequence of sequence S
indicates the second largest one while sorting all the increasing
subsequences of S by its length.
Each
test case begins with an integer N, indicating the length of the
sequence. Then N integer Ai follows, indicating the sequence.
[Technical Specification]
1. 1 <= T <= 100
2. 2 <= N <= 1000
3. 1 <= Ai <= 1 000 000 000
2
1 1
4
1 2 3 4
5
1 1 2 2 2
3
2
For the first sequence, there are two increasing subsequence: [1], [1]. So the length of the second longest increasing subsequence is also 1, same with the length of LIS.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = ;
int dp[N],num[N];
int a[N];
int main(){
int tcase;
scanf("%d",&tcase);
while(tcase--){
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
}
int ans = dp[] = num[]= ;
for(int i=;i<=n;i++){
dp[i] =num[i]= ;
for(int j=;j<i;j++){
if(a[i]>a[j]){
if(dp[i]==dp[j]+){
num[i]+=num[j];
}
if(dp[i]<dp[j]+){
dp[i] = dp[j]+;
num[i] = num[j];
}
}
}
ans = max(ans,dp[i]);
}
int cnt=;
for(int i=;i<=n;i++){
if(dp[i]==ans){
cnt+=num[i];
}
}
if(cnt==) printf("%d\n",ans-);
else printf("%d\n",ans);
}
return ;
}
最新文章
- 【转】Hadoop FS Shell命令
- ionic配置 问题小记
- Hadoop集群datanode磁盘不均衡的解决方案
- C++设计模式-Mediator中介者模式
- linux命令行下载jdk
- BZOJ1030——文本生成器
- 基于ubuntu-2.6.35内核的SDIO-WiFi驱动移植
- 观察器observes与对象初始化
- c++11之智能指针
- STL set_difference set_intersection set_union 操作
- C++设计模式-Iterator迭代器模式
- 689C - Mike and Chocolate Thieves 二分
- Logback日志基础配置以及自定义配置
- VS2017 性能优化方法
- Anaconda与Spyder升级命令
- Linux运行模式
- Android_编程开发规范
- 解决vmware与主机无法连通的问题
- Java知多少(91)对话框
- 176条DevOps人员常用的linux命令速查表
热门文章
- 关于Android SDK无法更新的解决办法
- 获取<;考试>;博文密码!o(*≧▽≦)ツ
- Hadoop学习笔记系列
- Spark Streaming实例
- IOS客户端的个人中心可以查看自己的博客了。
- 剑指Offer - 九度1351 - 数组中只出现一次的数字
- 更改maven本地仓库地址
- Java面试准备十六:数据库——MySQL性能优化
- iptables的配置文件/etc/sysconfig/iptables不存在 linux防火墙开关命令
- 转换 nvarchar 值 &#39;2013071200000578&#39; 时溢出了整数列