题意：给定两个字符串(可能为空串)，求这两个串交叉组成新串的子串中的回文串的最大长度。

布尔型变量dp[i][j][k][l]表示串a从i到j，b从k到l能否组成新串，初始化为false,则采取区间动态规划。(从1计数)

1 #include<algorithm>

 2 #include<cmath>

 3 #include<cstdio>

 4 #include<cstdlib>

 5 #include<cstring>

 6 #include<iostream>

 7 #include<map>

 8 #include<queue>

 9 #include<string>

 #include<vector>

 typedef long long LL;

 using namespace std;

 

 char a[], b[];

 const int N = , INF = 0x3F3F3F3F;

 bool dp[][][][];

 

 int main(){

     while(gets(a + ) && gets(b + )){

         int la = strlen(a + );

         int lb = strlen(b + );

         memset(dp, , sizeof(dp));

 

         for(int i = ; i <= la + ; i++){

             for (int j = ; j <= lb + ; j++){

                 dp[i][i][j][j - ] = dp[i][i - ][j][j] = dp[i][i - ][j][j - ] = ;

             }

         }

 

         int ans = ;

         for(int l1 = ; l1 <= la; l1++){

             for(int l2 = ; l2 <= lb; l2++){

                 for(int i = , j = i + l1 - ; j <= la; i++, j++){

                     for(int k = , l = k + l2 - ; l <= lb; k++, l++){

                         if(!dp[i][j][k][l]){

                         bool b1 = i <= j && a[i] == a[j] && dp[i + ][j - ][k][l];

                         bool b2 = k <= l && b[k] == b[l] && dp[i][j][k + ][l - ];

                         bool b3 = l >  && a[i] == b[l] && dp[i + ][j][k][l - ];

                         bool b4 = j >  && b[k] == a[j] && dp[i][j - ][k + ][l];

                         dp[i][j][k][l] = b1 || b2 ||b3 ||b4;

                         }

                         if(dp[i][j][k][l]  && l1 + l2 > ans){

                             ans = l1 + l2;

                         }

                     }

                 }

             }

         }

         printf("%d\n", ans);

     }

     return ;

 }