首页 > 代码库 > uva 1471
uva 1471
LIS变形,最后一个循环i是长度,d[i]存储的是相同长度最小的最后一个元素,也就是啊a[i],然后和
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int maxn=200000+10; int a[maxn],f[maxn],g[maxn]; int d[maxn]; const int inf=0x3f3f3f3f; int t,n; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); memset(d,inf,sizeof(d)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[1]=1; for(int i=2;i<=n;i++) { if(a[i]>a[i-1]) f[i]=f[i-1]+1;//上升到a[i]的最大长度 else f[i]=1; } g[n]=1; for(int i=n-1;i>=1;i--) { if(a[i]<a[i+1]) g[i]=g[i+1]+1;//a[i]开始上升的最大长度 else g[i]=1; } int ans=0; for(int i=1;i<=n;i++) { int len=lower_bound(d+1,d+1+i,a[i])-(d+1)+g[i];//g[i]对应a[i],要找到a[i]对应的f[i] ans=max(ans,len); d[f[i]]=min(d[f[i]],a[i]);//更新相同长度的最小a[i],让d[i]=它 } printf("%d\n",ans); } return 0; }
g[i]衔接
uva 1471
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。