最长单调递增子序列 应该算是比较经典的问题 记录一下我写这道题的过程吧
首先转换成lcs的做法 我就不说了 我觉得很内个啥 你懂吧 就复杂度依然是n方 很麻烦的方法
方法一 动态规划 O(n*n)
思路是这样的 定义dp[i] 为在I点结束的最长单调递增子序列的长度 所以可以便利一遍数组 每次都把之前的东西都找一遍 尝试增大 就这样
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;const int N = 10005;int main(){int dp[N], t, maxx;char str[N];cin >> t ;while ( t -- ) {maxx = 0;cin >> str ;int len = strlen(str);memset(dp , 0, sizeof(dp));for (int i = 0; i < len; i ++) {for (int j = 0; j < i ; j ++) {if(str[j] < str[i])dp[i] = max(dp[i] , dp[j] + 1);maxx = max(maxx , dp[i]);}}cout << maxx + 1 << endl;}return 0;
百度了下O(n*lgn)的算法思想 然后自己写了一发
参考了这个人的博客 非常详细 不会都难！！！
这个人的~~
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio>using namespace std;const int N = 10005;char tar[N];char str[N];int Binary_search(int l,int r,char c){int mid;while (l < r) {mid = (l + r) >> 1;if(tar[mid] < c) {l = mid + 1;} else if (tar[mid] > c) {r = mid;} else return mid;}//cout << "mid == " << mid << endl;return l;}int main(){int t ;cin >> t ;while ( t -- ) {cin >> str ;int length = strlen(str);int len = 0;tar[len ++] = str[0];for (int i = 1; i < length; i ++) {if(str[i] > tar[len - 1]) {tar[len ++] = str[i];}else {int pos = Binary_search(0 , len, str[i]);tar[pos] = str[i];}}cout << len << endl;}}
