#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <
string>
#include <stack>
#include <queue>
#include <
set>
#include <sstream>
#include <map>
#include <bitset>
using namespace std ;
#define zero {0}
#define INF 2000000000
#define eps 1e-6
typedef long long LL;
int Max=
0;
char a[
1000];
int n;
char it[
100];
int f(
string s)
{
//cout<<s<<endl;
int len=
s.size();
int i,j,k;
int maxx=
1;
string ss=
"";
string re;
for(i=
0;i<len;i++
)
{
ss+=
s[i];
for(j=i+
1;j<len;j++
)
{
ss+=
s[j];
// cout<<ss<<endl;
re=
ss;
reverse(re.begin(),re.end());
if(ss==
re)
{
maxx=max(
int(ss.size()),maxx);
}
}
ss=
"";
}
return maxx;
}
void dfs(
int i)
{
if (i!=
n)
{
a[i]=
'a';
dfs(i+
1);
a[i]=
'b';
dfs(i+
1);
}
else
{
if(f(
string(a))<
Max)
{
Max=f(
string(a));
strcpy(it,a);
//printf("%s-------%d\n",a,Max);
}
}
}
int main()
{
#ifdef DeBUG
freopen("C:\\Users\\Sky\\Desktop\\1.in",
"r",stdin);
//freopen("C:\\Users\\Sky\\Desktop\\打表.txt","w",stdout);//PLEASE DELETE IT!!!!!!!!!!!!!!!!!!!!!!!!
#endif
int i,j,k;
string s;
for(i=
1;i<=
20;i++
)
{
Max=
INF;
memset(a,0,
sizeof(a));
n=
i;
printf("*****************长度%d\n",i);
dfs(0);
printf("%s\n",it);
}
return 0;
}
View Code
由a，b组成的包含最短的（最长回文子串）的序列，写这个暴力是解决一道题的关键hdu4731
转载于:https://www.cnblogs.com/Skyxj/p/3321644.html
