锐客网

  1. 首页 > it技术 > >

BZOJ 1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛|动态规划

刷水又来了一发

裸的最长上升子序列
然而我并没有写二分而是写的暴力
【BZOJ 1669: [Usaco2006 Oct]Hungry Cows饥饿的奶牛|动态规划】

#include #include #include #include #include #include #include #include #include #include #define T 5050 using namespace std; int sc() { int i=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar(); return i; } int a[T],f[T],st[T]; int top,n,ans; int search(int x) { int l=1; while(l<=top&&x>st[l])l++; if(l>top)st[++top]=x; else st[l]=x; return l; } int main() { n=sc(); for(int i=1; i<=n; i++)a[i]=sc(); for(int i=1; i<=n; i++)f[i]=search(a[i]),ans=max(f[i],ans); cout << ans; return 0; }



    推荐阅读


    上一篇：笔记|试分析培正强智教务系统选课卡顿的原因

    下一篇：Ubuntu 16.04 安装 google chrome