POJ 3903 Stock Exchange 【最长上升子序列】模板题

<题目链接>

题目大意:

裸的DP最长上升子序列,给你一段序列,求其最长上升子序列的长度,n^2的dp朴素算法过不了,这里用的是nlogn的算法,用了二分查找。

O(nlogn)算法

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N= 1e5+;
int a[N],rise[N]; int main(){
int n;while(~scanf("%d",&n)){
memset(rise,,sizeof(rise));
for(int i=;i<n;i++)scanf("%d",&a[i]);
int len=;
rise[]=-1e9;
for(int i=;i<n;i++){
if(a[i]>rise[len])rise[++len]=a[i];
else{
int j=lower_bound(rise+,rise++len,a[i])-rise;
rise[j]=a[i];
}
}
printf("%d\n",len);
}
}

虽然(n^2)算法过不了此题,但是还是先记录下

#include<cstdio>
int main()
{
int i, j, n;
int dp[], a[];
while (scanf("%d", &n) != EOF)
{
int max = ;
for (i = ; i<n; i++)
scanf("%d", &a[i]);
dp[] = ;
for (i = ; i<n; i++)
{
dp[i] = ;
for (j = ; j<i; j++)
if (a[j]<a[i] && dp[j] + >dp[i])
dp[i] = dp[j] + ;
}
for (i = ; i<n; i++)
if (max<dp[i])
max = dp[i];
printf("%d\n", max);
}
}
上一篇:Maven构建时跳过部分测试


下一篇:duang~免费的学习视频来啦:学霸君之全栈测试