题意:找出最长上升连续子序列(5,6,7,8…)
题解:直接用一个map映射每一个的值,递推计算出以每个值为结尾的序列长度,另外有很多map是未初始化的,大概在cf上都默认为0;
一开始用了O(n^2)的LIS改了条件保存路径输出,TLE了,后来用了排序递推,WA了
[coo]
#include
using namespace std;
int arr[200100],N,r,k,last,t,i;
map m;
int main(){
for(cin>>N; i>arr[i];
r=m[arr[i]]=m[arr[i]-1]+1;//r=该值=上值-1
if(r>k) k=r, last=arr[i];//最大值为下标为r,最大值为last
}
for(cout<

发表评论

邮箱地址不会被公开。 必填项已用*标注