锐客网

  1. 首页 > it技术 > >

bzoj|bzoj 1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛【dp+树状数组+hash】

最长上升子序列。虽然数据可以直接n方但是另写了个nlogn的
转移：f[i]=max(f[j]+1)(a[j] O(n^2)

#include #include using namespace std; const int N=5005; int n,a[N],f[N],ans; int read() { int r=0,f=1; char p=getchar(); while(p>'9'||p<'0') { if(p=='-') f=-1; p=getchar(); } while(p>='0'&&p<='9') { r=r*10+p-48; p=getchar(); } return r*f; } int main() { n=read(); for(int i=1; i<=n; i++) a[i]=read(); for(int i=1; i<=n; i++) { for(int j=0; j

O(nlogn)树状数组+hash
#include #include #include #include using namespace std; const int N=5005; int n,a[N],f[N],ans,g[N],t[N]; mapmp; int read() { int r=0,f=1; char p=getchar(); while(p>'9'||p<'0') { if(p=='-') f=-1; p=getchar(); } while(p>='0'&&p<='9') { r=r*10+p-48; p=getchar(); } return r*f; } inline int lb(int x) { return x&(-x); } void update(int x,int v) { for(int i=x; i<=n; i+=lb(i)) t[i]=max(t[i],v); } int ques(int x) { int re=0; for(int i=x; i>=1; i-=lb(i)) re=max(re,t[i]); return re; } int main() { n=read(); for(int i=1; i<=n; i++) a[i]=g[i]=read(); sort(g+1,g+1+n); for(int i=1; i<=n; i++) mp[g[i]]=i; for(int i=1; i<=n; i++) a[i]=mp[a[i]]; for(int i=1; i<=n; i++) { f[i]=ques(a[i]-1)+1; update(a[i],f[i]); ans=max(ans,f[i]); } printf("%d\n",ans); return 0; }

【bzoj|bzoj 1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛【dp+树状数组+hash】】转载于:https://www.cnblogs.com/lokiii/p/8964571.html

    推荐阅读


    上一篇：GLSL|GLSL ES 3.0 和 2.0 的区别

    下一篇：搭建OpenGL|搭建OpenGL ES开发环境