hdu5748（最长不下降序列）

本文主要是介绍hdu5748（最长不下降序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接:点击打开链接

//hdu5748
//题目大意：（证明略）一段序列，求以某个数结尾的严格最长不下降序列的长度
//大概思路：f[k],以f[k]结尾长度为k的不下降序列的末尾元素
//          lower_bound()找到第一个大于等于它的元素的下标#include <iostream>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define N 100020using namespace std;int f[N], ans[N], n, a, l;int main()
{int T; scanf("%d", &T);while(T--){memset(f, 0, sizeof(f));scanf("%d%d", &n, &a);f[1]= a; l= 1; ans[1]= 1;for(int i= 2; i<= n; i++){scanf("%d", &a);if(a> f[l]) { f[++l]= a; ans[i]= l; }else{int j= lower_bound(f+ 1, f+ l+ 1, a)- f;f[j]= a;if(j> l) ans[i]= l; else ans[i]= j;}}printf("%d", ans[1]);for(int i= 2; i<= n; i++) printf(" %d", ans[i]);printf("\n");}return 0;
}

这篇关于hdu5748（最长不下降序列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---