[数据结构与算法]蓝桥杯 真题 试题 历届真题 蓝肽子序列【第十一届】【决赛】【研究生组】

拿下拿下

题目

思路

与最长公共子序列的思路一样，只是将对字符的比较换成了对单词的比较。DP数组的维度也变成了单词的个数。只需要将两个序列的单词分别取出来存进容器里即可。

代码

#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;

string s1,s2;

void get(string s,vector<string> &l) //把每个蓝泰序列中的蓝泰拿出来放进vector 
{
  
  int i=0;
  while(i<s.length())
  {
    if(s[i]>='A'&&s[i]<='Z')
    {
    	
    	string ans;
    	ans+=s[i];i++;
    	while(s[i]>'Z')
    	{
    		ans+=s[i];
    		i++;
    	}
    	l.push_back(ans);
    }
  }

}

int main()
{
  // 请在此输入您的代码
  cin>>s1>>s2;
  vector<string> ss1;
  vector<string> ss2;
  get(s1,ss1);get(s2,ss2);
  int n=ss1.size();int m=ss2.size();
  int dp[n+1][m+1];
  for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++)
      dp[i][j]=0;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=m;j++)
    {
      if(ss1[i-1]==ss2[j-1])
      {
        dp[i][j]=dp[i-1][j-1]+1;
      }
      else
        dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
    }
  }
  cout<<dp[n][m]<<endl;

  return 0;
}