河南网站建设的详细策划,杭州做网站哪家好,私人影吧服务器,网站开发付款方法一#xff1a; 二分 我们可以知道 最长上升子序列的 最后一个数的值是随序列的长度而递增的 #xff08;呃呃呃 意会意会#xff09; 然后我们就可以二分找值了#xff08;并更新#xff09; //By SiriusRen
#include cstdio
#include cstring
#incl… 方法一 二分 我们可以知道 最长上升子序列的 最后一个数的值是随序列的长度而递增的 呃呃呃 意会意会 然后我们就可以二分找值了并更新 //By SiriusRen
#include cstdio
#include cstring
#include algorithm
using namespace std;
int n,cases,a[100050],f[100050],vis[100050];
int search(int x){int l0,rn,ans0;while(lr){int mid(lr)1;if(vis[mid]x)lmid1,ansmid;else rmid-1;}return ans;
}
int main()
{scanf(%d,cases);while(cases--){memset(f,0,sizeof(f));memset(vis,0x3f,sizeof(vis)),vis[0]0;scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);for(int i1;in;i){f[i]search(a[i])1;vis[f[i]]min(vis[f[i]],a[i]);}for(int i1;in;i)f[n]max(f[n],f[i]);printf(%d\n,f[n]);}
} 方法二 线段树 按照权值建 查询前一段中的最大值。。并插入当前的值,, //By SiriusRen
#include cstdio
#include cstring
#include algorithm
using namespace std;
int n,cases,a[100050],f[100050],xx,tree[666666];
void insert(int l,int r,int pos){if(lr){tree[pos]f[xx];return;}int mid(lr)1,lsonpos1,rsonpos1|1;if(mida[xx])insert(mid1,r,rson);else insert(l,mid,lson);tree[pos]max(tree[lson],tree[rson]);
}
int query(int l,int r,int pos){if(ra[xx])return tree[pos];int mid(lr)1;if(mida[xx])return max(query(l,mid,pos1),query(mid1,r,pos1|1));else return query(l,mid,pos1);
}
int main(){scanf(%d,cases);while(cases--){memset(tree,0,sizeof(tree));memset(f,0,sizeof(f));scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);for(xx1;xxn;xx){f[xx]query(1,n,1)1;insert(1,n,1);}for(int i1;in;i)f[n]max(f[n],f[i]);printf(%d\n,f[n]);}
} 转载于:https://www.cnblogs.com/SiriusRen/p/6532290.html
