洛谷一题超时

常规
1

这个是题目

#include<bits/stdc++.h>
using namespace std;
int a[100001],b[100001],l,k,n,maxx;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		b[i]=1;
	}
	for(int i=n-1;i>=1;--i)
	{
		maxx=0;
		for(int j=i+1;j<=n;++j)
		if(a[j]>a[i]&&b[j]>maxx) maxx=b[j];
		b[i]+=maxx;
		l=max(l,b[i]);
	}
	cout<<l;
	return 0;
}
5 个赞
2

要用二分优化

4 个赞
3

动态规划怎么二分

5 个赞
4

这是AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1e5+10;
ll n,a[N],l,r,mid,ans,dp[N],ret[N],p[N],s;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		l=1,r=ans;
		while(l<=r){
			mid=l+r>>1;
			if(dp[mid]<a[i]) l=mid+1;
			else r=mid-1;
		}
		dp[l]=a[i];
		ans=max(ans,l);
		ret[i]=l;
	}
	cout<<ans;	
	return 0;
}
5 个赞
5

设 dp[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值

4 个赞
6

蟹蟹我知道了

5 个赞
7

dp数组是单调的

6 个赞
8

所以可以二分

6 个赞
12

还可以使用树状数组

4 个赞