装修公司做网站的好处,一个网站用多少数据库表,室内装修设计软件免费版下载破解版,html5 网站题号#xff1a;NC13230 名称#xff1a;合并回文子串 来源#xff1a;美团2017年CodeM大赛-初赛A轮 题目链接 时间限制#xff1a;C/C 2秒#xff0c;其他语言4秒 空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K 64bit IO Format: %lld 题目描述 输入两个字…题号NC13230 名称合并回文子串 来源美团2017年CodeM大赛-初赛A轮 题目链接 时间限制C/C 2秒其他语言4秒 空间限制C/C 262144K其他语言524288K 64bit IO Format: %lld 题目描述 输入两个字符串A和B合并成一个串C属于A和B的字符在C中顺序保持不变。如abc和xyz可以被组合成axbycz或abxcyz等。 我们定义字符串的价值为其最长回文子串的长度回文串表示从正反两边看完全一致的字符串如aba和xyyx。 需要求出所有可能的C中价值最大的字符串输出这个最大价值即可 输入描述: 第一行一个整数T(T ≤ 50)。 接下来2T行每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)A,B的字符集为全体小写字母。 输出描述:
对于每组数据输出一行一个整数表示价值最大的C的价值。 示例1
输入
2
aa
bb
a
aaaabcaa输出
4
5思路区间dp问题 dp[i][j][m][n]表示A中下标i到j-1以及B中下标m到n-1的串能否组成回文串 (dp值为零则表示不构成回文串不为零则表示构成) 首先字符本身是回文串 其次分为四种情况 a[i]a[j-1] dp[i][j][m][n]c[i1][j-1][m][n]; 因为dp我们只考虑是否为0或非0所以dp之间可以也可以|,都不影响 当A的第i为和第j-1位相同时那么dp[i][j]是否为回文串就取决于比它小一层的dp[i1][j-1]这样一次往里推就可以推到以一种情况 b[m]b[n-1] dp[i][j][m][n]c[i][j][m1][n-1]; (和上一个思路相同)
a[i]b[n-1] dp[i][j][m][n]c[i1][j][m][n-1]; 当A的i与B的n-1相同时那么dp[i][][][n]是否为回文串就取决于A的后一位i1和B的前一位n-1的情况 a[m]b[j-1] dp[i][j][m][n]c[i][j-1][m1][n]; 代码
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn60;
int dp[maxn][maxn][maxn][maxn];
int main()
{int t;cint;string a,b;while(t--){int mx0;cinab;for(int ti0;tia.length();ti)//第一个字符提供的长度{for(int tj0;tjb.length();tj){for(int i0;itia.length();i)//第一个字符为开头 {for(int j0;jtjb.length();j){int lenatii;//区间[i,lena-1] int lenbtjj; if(tjti1)dp[i][lena][j][lenb]1;else {dp[i][lena][j][lenb]0;if(ti2a[i]a[lena-1])dp[i][lena][j][lenb]|dp[i1][lena-1][j][lenb];if(tj2b[j]b[lenb-1])dp[i][lena][j][lenb]|dp[i][lena][j1][lenb-1];if(ti1tj1a[i]b[lenb-1])dp[i][lena][j][lenb]|dp[i1][lena][j][lenb-1];if(ti1tj1b[j]a[lena-1])dp[i][lena][j][lenb]|dp[i][lena-1][j1][lenb];}if(dp[i][lena][j][lenb])mxmax(mx,tjti);}}}}coutmxendl;}
}
/*
dp[i][lena][j][lenb]
*/另外 tj和tn从0开始不断讨论A中i到itj和B中m到tn的回文字符串
