今天做的是合并回文子串
虽说看到题目就知道是个dp，无奈写不出来。

首先来看题意：给两个字符串A和B，现在将A和B进行合并，要求两个字符串中原有的相对位置不发生变化，问合并的可能中最长的回文子串长度？
这里A和B的长度都不超过50.

题目类型：
区间DP

题解已经讲的很好了，这里做个总结：

  • 1.最长回文序列问题

    给一个字符串，求一个最长的回文子序列（不要求连续）。
    我们用dp[i][j]表示一个字符串从i-j的最长子序列长度。
    那么对于dp[i][j]
    若a[i]=a[j]则dp[i][j]=dp[i+1][j-1]+2
    若a[i]!=a[j]则dp[i][j]=max(dp[i+1][j],dp[i][j-1])
    因此我们可以在O(n^2)时间内解决这个问题。

    #include<bits/stdc++.h>
using namespace std;
string s,a;
int dp[100][100];
int main()
{
  cin>>s;
  int len=s.size();
  for(int i=0;i<len;i++)a[i+1]=s[i];
  for(int i=1;i<=len;i++){
      dp[i][i]=1;
  }
  for(int k=2;k<=len;k++){
      for(int i=1;i+k-1<=len;i++){
          int j=i+k-1;
          if(a[i]==a[j])dp[i][j]=dp[i+1][j-1]+2;
          else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
      }
  }
  cout<<dp[1][len]<<endl;
  return 0;
}

  • 2.最长回文子串问题

    给一个字符串，求一个最长的回文子串（要求连续）
    这里我们如果用dp[i][j]表示字符串从i-j的最长子串长度，会发现转移困难的问题，因为子串要求是连续的，如果简单的用dp[i+1][j]或者dp[i][j-1]转移是会出问题的，因为转移过来的不一定能保证是回文子串。
    因此我们重新定义dp[i][j]为字符串从i-j能否组成一个回文子串（相当于强制选择i和j两个位置），那么若a[i]=a[j]，则dp[i][j]=dp[i+1][j-1]
    若a[i]!=a[j]，则dp[i][j]=0
    这里有一道练习题，https://ac.nowcoder.com/acm/problem/14517
    代码如下：

    #include<bits/stdc++.h>
using namespace std;
string s,a;
int dp[1220][1220];
int main()
{
  while(cin>>s){
      memset(dp,0,sizeof(dp));
      int len=s.size();
      for(int i=0;i<len;i++)a[i+1]=s[i];
      for(int k=0;k<=len;k++){
          for(int i=1;i+k-1<=len;i++){
              int j=i+k-1;
                              if(k<=1){dp[i][j]=1;continue;}   //特判1个的时候
              if(a[i]==a[j]){
                   if(k>1)dp[i][j]=dp[i+1][j-1];
              }
              else dp[i][j]=0;
          }
      }
      int maxians=0;
      for(int i=1;i<=len;i++){
          for(int j=i;j<=len;j++){
              if(dp[i][j]){
                  maxians=max(maxians,j-i+1);
              }

          }
      }
      cout<<maxians<<endl;
  }

  return 0;
}

再回到这个问题，显然应该是一个最长回文子串问题。注意到长度不超过50。
我们令dp[i][j][k][l]表示A串中i-j部分和B串中k-l部分能否构成回文串。
那么我们可以得到4种情况：
<1>a[i]=a[j]
<2>a[i]=b[l]
<3>b[k]=a[j]
<4>b[k]=b[l]
分别进行讨论就好了，但是要考虑边界问题，这里采用了len1+len2<=1的时候直接令dp为1，直接把边界问题包括其中一个不选等问题解决了，还是很细节的。

#include<bits/stdc++.h>
using namespace std;
int dp[65][65][65][65];   //表示a[i.j]和b[k.l]能否组成最长回文子串
char a[55],b[55];
int main()
{
    int t;
    cin>>t;
    while(t--){
        memset(dp,0,sizeof(dp));
        scanf("%s",a+1);
        scanf("%s",b+1);
        int len1,len2,lena,lenb;
        lena=strlen(a+1);
        lenb=strlen(b+1);
        int maxians=0;
        for(int len1=0;len1<=lena;len1++){
            for(int len2=0;len2<=lenb;len2++){
                for(int i=1;i+len1-1<=lena;i++){
                    int j=i+len1-1;
                    for(int k=1;k+len2-1<=lenb;k++){
                        int l=k+len2-1;
                        int & tmp=dp[i][j][k][l];
                        if(len1+len2<=1)dp[i][j][k][l]=1;
                        else {

                        if(len1+len2<=1)tmp=1;
                        else {
                            if(a[i]==a[j]&&len1>1)tmp=max(tmp,dp[i+1][j-1][k][l]);
                            if(a[i]==b[l]&&len1&&len2)tmp=max(tmp,dp[i+1][j][k][l-1]);
                            if(b[k]==a[j]&&len1&&len2)tmp=max(tmp,dp[i][j-1][k+1][l]);
                            if(b[k]==b[l]&&len2>1)tmp=max(tmp,dp[i][j][k+1][l-1]);
                        }
                        }
                        if(tmp)maxians=max(maxians,len1+len2);
                    }
                }
            }
        }
        cout<<maxians<<endl;
    }
    return 0;
}