最长公共子序列，顾名思义当然是求两个字符串的最长公共子序列啦，当然，这只是一道非常菜的动规，所以直接附上代码：
#include<iostream> #include<cstdio> using namespace std; char a[100],b[100]; int dp[100][100]; int main() { int m,n; cin>>m>>n; for(int i = 1;i <= m;i ++) { cin>>a[i]; } for(int i = 1;i <= n;i ++) cin>>b[i]; for(int i = 1;i <= m;i ++) { for(int j = 1;j <= n;j ++) { dp[i][j] = max(dp[i-1][j],dp[i][j-1]); if(a[i] == b[j]) dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j]); } } cout<<dp[m][n]; return 0; }而最长回文子序列和第一道题有什么关系呢？答案其实很简单，只要把原来的字符串倒着保存一遍，然后进行第一题的比较就可以了，代码如下：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[100],b[100]; int dp[100][100]; int main() { int m; cin>>m; for(int i = 1;i <= m;i ++) { cin>>a[i]; } for(int i = 1;i <= m; i++) b[i] = a[m - i + 1]; for(int i = 1;i <= m;i ++) { for(int j = 1;j <= m;j ++) { dp[i][j] = max(dp[i-1][j],dp[i][j-1]); if(a[i] == b[j]) dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j]); } } cout<<dp[m][m]; return 0; }有了第二题的启发，最长上升和下降子序列也很好想了，就是把所得的字符串进行一次排序，再进行一次最长公共子序列就可以了，代码如下：
最长上升子序列： #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[100],b[100]; int dp[100][100]; int main() { int m; cin>>m; for(int i = 1;i <= m;i ++) { cin>>a[i]; b[i] = a[i]; } sort(b + 1,b + m +1); for(int i = 1;i <= m;i ++) { for(int j = 1;j <= m;j ++) { dp[i][j] = max(dp[i-1][j],dp[i][j-1]); if(a[i] == b[j]) dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j]); } } cout<<dp[m][m]; return 0; } 最长下降子序列： #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int a[100],b,c[100]; int dp[1000][1000]; int main() { cin>>b; for(int i = 0;i < b; i++) { cin>>a[i]; c[i] = a[i]; } sort(c,c + b); for(int i = 0;i < b; i++) { for(int j = b - 1;j >= 0; j--) { dp[i][j] = max(dp[abs(i - 1)][j],dp[i][j + 1]); if(a[i] == c[j]) dp[i][j] = max(dp[abs(i - 1)][j + 1] + 1,dp[i][j]); } } cout<<dp[b - 1][0]; return 0; }其实，还有一个nlogn的方法，只不过用了stl中的upper_bound;
用法：下表 = upper_bound(数组开头，数组结尾，查找值） - 数组名
和sort类似
#include<iostream>#include<cstdio>#include<algorithm> #include<cstring> using namespace std;int main(){ int a[100],m,d[100],l = 1,k; memset(d,0,sizeof(d)); cin>>m; for(int i = 0;i < m;i++) cin>>a[i]; d[1] = a[1]; for(int i = 1;i < m;i++) { if(a[i] >= d[l]) { l++; d[l] = a[i]; } else { k = upper_bound(d,d + l,a[i]) - d; d[k] = a[i]; } } cout<<l<<endl; return 0;}/*51 2 3 4 5*/
最后，姆爷镇楼！！！
转载于:https://www.cnblogs.com/DukeLv/p/8119817.html
