蓝桥杯 蓝肽子序列

与通常的最长子序列相比这里只是将单个字符替换成一个单词而已，拆分后使用动态规划和string自身支持的==对比进行判断即可。

#include <iostream>
using namespace std;
int dp[1005][1005] = {0};
int main()
{
  string aa[1000],bb[1000];//比使用vector写代码方便点
  string a,b;
  int cnta=0,cntb=0;
  cin>>a>>b;
  int j=0;//记录每个蓝肽首个大写字母位置
  for(int i=0;i<a.size();i++)
  {
    if((a[i]>='A')&&(a[i]<='Z')&&(i>0)) //大于0是为了防止第一个放入一个空的字符串
    {
        aa[cnta++] = (a.substr(j,i-j));j =i;//更新
    }
    
  }
  aa[cnta++] = a.substr(j);//放入最后一个
  j = 0;//初始化位置
  for(int i=0;i<b.size();i++)
  {
    if((b[i]>='A')&&(b[i]<='Z')&&(i>0)) //大于0是为了防止第一个放入一个空的字符串
    {
        bb[cntb++] = (b.substr(j,i-j));j=i;//更新
    }
    
  }
  bb[cntb++] = b.substr(j);//放入最后一个
  for(int i=1;i<=cnta;i++)
  {
  	for(int j=1;j<=cntb;j++)
  	{
  		if(aa[i-1] == bb[j-1]) dp[i][j] = dp[i-1][j-1]+1;
  		else
  		{
  			dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		  }
	  }
  }
  cout<<dp[cnta][cntb];
  return 0;
}