本文主要是介绍NYoj 214 单调递增子序列（二）[动态规划+二分]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*NYoj 214 单调递增子序列（二）相当于（一）的时间优化.并且应用了二分.也有动态规划的意思吧！
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
using namespace std;
int a[100010];
int b[100010];//b用来存储当前状态的最优串.//比如abef和abcd，abcd为最优串,而以后的更新只需要最优串.
int main()
{int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++)scanf("%d",&a[i]);b[1]=a[0];int length=1;int l,r,mid;for(int i=1;i<n;i++){l=1;r=length;while(l<=r){mid=(l+r)/2;if(b[mid]<a[i]) l=mid+1;else r=mid-1;}b[l]=a[i];if(l>length) length++;//新增的，说明最优串的长度变长了.}printf("%d\n",length);}
}
b数组中，得到的不的最后ans的子序列。这一点要清楚的明白。
这种二分的方法只能求得，最长的长度。
这篇关于NYoj 214 单调递增子序列（二）[动态规划+二分]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
