题解 CF1304B 【Longest Palindrome】
ShineEternal
2020-02-16 08:31:24
[可能更佳的阅读效果](https://blog.csdn.net/kkkksc03/article/details/104338145)
。
## description：
- 给你 $n$ 个长度为 $m$ 的字符串。
- 请你判断删去其中的几个（或者不删去），能使得将剩下字符串随意排列所形成的回文串长度最大。
- 请你输出最大的长度和那个回文串。
- $1\le n\le 100$，$1\le m\le 50$。
- translate by @[ShineEternal](https://www.luogu.com.cn/user/45475)。
## solution:
我们将字符串两两判断，是否有一个与另一个的倒序相等即可。
但是要注意可能可以在最中间填一个自身回文串，且最多填一个，所以还要考虑这种情况，把自身回文串找出来，如果有一个没被用过，那就填进去即可。
## code：
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
char s[105][55],sx[105][55];
int mp[1005];
int a[1005];
int m;
int check(int i,int j)
{
for(int k=0;k<m;k++)
{
if(s[i][k]!=s[j][m-k-1])return 0;
}
return 1;
}
int main()
{
int n;
scanf("%d%d",&n,&m);
int tmp=-1;
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]);
}
/*for(int i=1;i<=n;i++)
{
for(int j=0;j<m;j++)
{
int k=m-j-1;
sx[i][j]=s[i][k];
}
}*/
int cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
//cout<<s[i]<<endl;
if(check(i,j))
{
// printf("%d %d\n",i,j);
a[++cnt]=i;
a[++cnt]=j;
//printf("cnt=%d\n",cnt);
//ans++;
}
}
}
for(int i=1;i<=cnt;i++)
{
mp[a[i]]=1;
}
//printf("mp=%d\n",mp[4]);
for(int i=1;i<=n;i++)
{
if(mp[i]!=1)
{
//printf("i=%d\n",i);
int tag=0;
for(int j=0;j<m;j++)
{
if(s[i][j]!=s[i][m-j-1])
{
tag=1;
break;
}
}
if(tag==0)
{
tmp=i;
}
}
}
//printf("tmp=%d\n",tmp);
if(tmp!=-1)
printf("%d\n",(cnt+1)*m);
else
printf("%d\n",cnt*m);
for(int i=1;i<=cnt;i++)
{
if(i%2==1)
{
//if(a[i]==tmp)flag=1;
printf("%s",s[a[i]]);
}
//cout<<s[a[i]];
}
if(tmp!=-1)
{
printf("%s",s[tmp]);
}
for(int i=cnt;i>=2;i--)
{
if(i%2==0)
{
// if(a[i]==tmp)flag=1;
printf("%s",s[a[i]]);
}
}
printf("\n");
return 0;
}
```