hdu 5748(LIS)
2024-08-25 09:26:34
Bellovin
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 302 Accepted Submission(s): 148
Problem Description
Peter has a sequence a1,a2,...,an and he define a function on the sequence -- F(a1,a2,...,an)=(f1,f2,...,fn), where fi is the length of the longest increasing subsequence ending with ai.
Peter would like to find another sequence b1,b2,...,bn in such a manner that F(a1,a2,...,an) equals to F(b1,b2,...,bn). Among all the possible sequences consisting of only positive integers, Peter wants the lexicographically smallest one.
The sequence a1,a2,...,an is lexicographically smaller than sequence b1,b2,...,bn, if there is such number i from 1 to n, that ak=bk for 1≤k<i and ai<bi.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first contains an integer n (1≤n≤100000) -- the length of the sequence. The second line contains n integers a1,a2,...,an (1≤ai≤109).
Output
For each test case, output n integers b1,b2,...,bn (1≤bi≤109) denoting the lexicographically smallest sequence.
Sample Input
3
1
10
5
5 4 3 2 1
3
1 3 5
1
10
5
5 4 3 2 1
3
1 3 5
Sample Output
1
1 1 1 1 1
1 2 3
1 1 1 1 1
1 2 3
题意:求以ai(0<i<n)结尾的最长上升子序列的个数.
题解:在LIS的O(n*log(n))的模板里面找到加一个dp数组记录每一位的最长上升子序列个数,顺序输出即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>
using namespace std;
const int N = ;
int a[N];
int dp[N],c[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 MAX = ,j=;
c[] = a[];
dp[] = ;
for(int i=; i<=n; i++)
{
if(a[i]<=c[]) j = ;
else if(a[i]>c[MAX]) j = ++MAX;
else j = lower_bound(c+,c++MAX,a[i])-c;
c[j] = a[i];
dp[i] = j;
}
for(int i=; i<n; i++)
{
printf("%d ",dp[i]);
}
printf("%d\n",dp[n]);
}
return ;
}
最新文章
- html5 canvas常用api总结(二)--绘图API
- 【WPF系列】基础 PasswordBox
- net对XML增删改查
- Matrix_二维树状数组
- 转 oracle 11g 导出空表
- CodeFile与CodeBehind的区别
- QSqlDatabase的进一步封装(多线程支持+更加简单的操作)——同时支持MySQL, SQL Server和Sqlite
- cmd命令添加一个应用程序到防火墙例外项中
- TMT行业分析师
- Keil中使用宏编译来定义DEBUG输出
- centos7使用cobbler(2.8)批量部署操作系统之二
- WAMPServer多站点配置方法
- java Serializable 生成随机序列
- C++ Thrift服务端记录调用者IP和被调接口方法
- notepad++ 注释
- Python——运算符
- APPlication,Session和Cookie的区别
- 多版本opencv管理; find_package()的原理解析
- 第二章 FFmpeg常用命令
- 最简单例子图解JVM内存分配和回收(转)