简单网/seo百度排名优化

先留一篇很好的文章，
下面只是为了加深印象所记录的一个例题，以及一些自己的总结传送门
这里再加一种方法，就是再开一个数组，将原理的数组复制进去后，按升序进行排序，求这两个串的LCS
O(n^2)朴实双循环的模板

#include <iostream>
#include <algorithm>
#include <string.h>#define MAXN 1000+5
#define INF INT_MAXusing namespace std;int dp[MAXN],a[MAXN];int main(){int n;while(cin>>n,n){int maxx = 0;memset(dp,1,sizeof(dp));for(int i = 1; i <= n; i++){cin>>a[i];}for(int i = 1; i <= n; i++){for(int j = 1; j < i; j++){if(a[i] > a[j]){dp[i] = max(dp[j] + 1,dp[i]);}}}maxx = dp[1];for(int i = 1; i <= n; i++){maxx = max(maxx,dp[i]);}cout<<maxx<<endl;}return 0;
}

O(n*logn)二分加贪心模板

int dp[MAXN],a[MAXN];
int Lis(int n){int l = 1;dp[1] = a[1];for(int i = 2; i <= n; i++){if(a[i] > dp[l]){l++;dp[l] = a[i];}else{int pos = lower_bound(dp + 1,dp + l,a[i]) - dp;dp[pos] = a[i];}}return l;
}main函数for(int i = 1; i <= t; i++){cin>>a[i];}int maxx = Lis(t);

关于O（n ^ 2）于O（n*logn）的算法，尽量多去使用贪心二分查找的方法，但是要注意，这种方法，其中用来维护的dp数组内的序列不一定是正确的答案，只是里面元素的数量是正确答案，所以如果要是求有关具体值时，则必须用O（n ^2）的算法。
学到了两个二分查找的函数，不用自己写轮子了（狗头）函数传送门
至于线段树的优化，等学习了数据结构之后再进行学习吧（捂脸）

题目链接HDU1087 Almost Sorted Array
这类题就是要求关于LIS具体值，需要用双重循环

#include <iostream>
#include <algorithm>
#include <string.h>#define MAXN 1000+5
#define INF INT_MAXusing namespace std;int dp[MAXN],a[MAXN];int main(){int n;while(cin>>n,n){int maxx = 0;memset(dp,0,sizeof(dp));for(int i = 1; i <= n; i++){cin>>a[i];}dp[1] = a[1];for(int i = 1; i <= n; i++){for(int j = 1; j < i; j++){if(a[i] > a[j]){dp[i] = max(dp[j] + a[i],dp[i]);}}dp[i] = max(a[i],dp[i]);//防止在前i个数中没有递增序列，这样就取当前的a[i]值}maxx = dp[1];for(int i = 1; i <= n; i++){maxx = max(maxx,dp[i]);}cout<<maxx<<endl;}return 0;
}

二分加贪心优化的LIS例题

Bridging signals

#include <iostream>
#include <algorithm>
#include <string.h>#define MAXN 40000+5
#define INF INT_MAXusing namespace std;int dp[MAXN],a[MAXN];int Lis(int n){int l = 1;dp[1] = a[1];for(int i = 2; i <= n; i++){if(a[i] > dp[l]){l++;dp[l] = a[i];}else{int pos = lower_bound(dp + 1,dp + l,a[i]) - dp;dp[pos] = a[i];}}return l;
}int main()
{int n;cin>>n;while(n--){int t;cin>>t;memset(dp,0,sizeof(dp));for(int i = 1; i <= t; i++){cin>>a[i];}int maxx = Lis(t);cout<<maxx<<endl;}return 0;
}