MY CODE:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<stdio.h> //nlogn算法 /*把10000搞成1000了，错了一下午*/ int n,max; int b[10001],a[10001],len[10001]; int bins(int key) { static int l,r,y; l=0;r=n; while (l<=r){ y=(l+r)>>1; if (b[y]>key) r=y-1;else if (b[y]<key) {if (b[y+1]>key) return y;else l=y+1;}//这里大括号为了阅读方便 else return y; } } int main(){ int i,j; scanf("%d\n",&n); for (i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=20000;} b[0]=0;//这个初始化要比所有元素小 for (i=1;i<=n;i++){ len[i]=bins(a[i]-1)+1; if (len[i]>max) max=len[i]; if (b[len[i]]>a[i]) b[len[i]]=a[i]; } printf("%d",max); return 0; } |
题目描述
镇里举办贪吃比赛，一共比赛N天，规定：每次吃的必须比上次多，一天只能吃一次（撑死…），吃的天数最多的人将获得胜利，获得10000000000 mod 10 的奖金^_^ 现在，Sally要参加比赛，她邀请参加OI的你一起帮忙，胜利后七三分成^_^
输入格式
第一行一个数N，表示吃的天数（N<=10000) 第二行N个数，表示每天能吃的数量（数量最多10000）
输出格式
一个数，表示最多吃的天数
样例输入
样例输出
原创文章，转载请注明： 转载自Comzyh的博客
本文链接地址: P156 吞噬比赛 NlogN最长不下降子序列