单调递增最长子序列
时间限制: 3000 ms | 内存限制:65535 KB
难度: 4
3 aaa ababc abklmncdefg</dd> <dt> 样例输出 </dt> <dd>
1 3 7</dd> <dt> 来源 </dt> <dd> 经典题目 </dd> <dt> 上传者 </dt> <dd> iphxer </dd> <dd> 先用之前学过的方法做过一遍,这个的时间复杂度是O(n²),从挑战程序设计竞赛上看到竟然还有O(nlogn)的方法!! </dd> <dd>
#include <iostream> #include <cstdio> #include <cstring> using namespace std; char a[10005]; int b[10005]={0}; int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++){ int ans=1; scanf("%s",a); int len=strlen(a); fill(b,b+len,1); for(int j=1;j<len;j++){ int maxx=0; for(int k=0;k<j;k++){ if(a[k]<a[j]){ maxx=max(b[k],maxx); } } b[j]=maxx+1; ans=max(b[j],ans); } printf("%d\n",ans); } return 0; }
这是O(nlogn)的方法,利用lower_bound()函数。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 //solve()需要三个全局 9 char a[10005]; 10 int b[10005]={0}; 11 const int INF=9999999; 12 int len; 13 14 void solve(){ 15 fill(b,b+len,INF); 16 for(int i=0;i<len;i++){ 17 *lower_bound(b,b+len,a[i])=a[i];//这里在比较的时候是以a[i]的ascii值比较的 18 } 19 printf("%d\n",lower_bound(b,b+len,INF)-b); 20 } 21 22 int main() 23 { 24 int n; 25 scanf("%d",&n); 26 for(int i=0;i<n;i++){ 27 scanf("%s",a); 28 len=strlen(a); 29 solve(); 30 } 31 return 0; 32 }
</dd> </dl>