简单动态规划——最长公共子序列&&最长回文子序列&&最长上升||下降子序列
最长公共子序列，顾名思义当然是求两个字符串的最长公共子序列啦，当然，这只是一道非常菜的动规，所以直接附上代码：
#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;
}
/*
5
1 2 3 4 5
*/
最后，姆爷镇楼！！！