蓝桥杯算法提高VIP-聪明的美食家 （C语言代码）

/*为啥错。。。。*/
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[1002];
int lis(){
	int length=1,L[1002];
	L[0]=a[0];
	for(int i=1;i<n;i++){
		/*如果当前长度为length的数组的第length-1值小于A,就将A入数组,L维护一个递增序列*/
		if(L[length-1]<a[i]) L[length++]=a[i];
		/*否则在数组L中二分查找第一个比a[i]大于或等于的a[i]的位置数下标L[i]，并将其赋值为a[i]*/
		/*不会真正找到递增子序列，只会找到其对应长度。例如：3 7 8 2 4 的递增子序列长度为3 L存的数为{2,4,8}，将2替换了3将4替换了7*/
		else *lower_bound(L,L+length,a[i])=a[i]; 
	}
	return length;

}
int main(){
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	cout<<lis()<<endl;
    return 0;
}

/*借鉴wu的*/
/*
思路：变量b[1002]，b[i]:表示数组长度为i+1的不降序列
每次外层循环遍历到i时，从内层循环j从0遍历到i中查找此时比i小的数，
如果小的话，将此时b[j]加1 并且与原b[i]比较
取最大值。
例如：3 2 4 5 7 8 初始b[]={1};
开始遍历，
i=0时，b[0]=1;
i=1时，b[1]=1;(在j=0--i中没比2小的)
i=2时，b[2]=2;(在j=0--i中找到比4小的其中为a[0]=3和a[1]=2且他们的b都是1,
所以此时b[2]=max(b[2],b[0]+1)=2然后循环j+1，b[2]=max(b[2],b[1]+1))=2。
依次下去。
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[1002],b[1002];
int main(){
	cin>>n;
	for(int i=0;i<n;i++){ cin>>a[i];b[i]=1;}
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			if(a[i]>=a[j]) b[i]=max(b[i],b[j]+1);
		}
	}
	sort(b,b+n);
	cout<<b[n-1]<<endl;
    return 0;
}

解题思路:

注意事项:





参考代码: