142.买帽子

2980 买帽子

 

 时间限制: 2 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

题解

 查看运行结果

题目描述 Description

      小A想买一顶新帽子，商店里有n个帽子 (1<=n<=100)，每顶帽子上有一个字符串，字符串的长度为len (1<=len<=500)。她认为每顶帽子上的字符串看起来越对称则代表这顶帽子更漂亮。根据每个字符串，我们可以算出其对称系数k (即最长对称子序列的长度) 来比较各顶帽子在小A心中的漂亮程度。

      例如，字符串 character (k=5) 比 pollution (k=4) 更对称，apple (k=2) 比 pear (k=1) 更对称。

      现在给定n个字符串，请将它们按对称系数排序后从大小输出 (k相同时按字典序排序)。

输入描述 Input Description

输入数据第一行只有一个n，表示有个字符串。

接下来有n行，每行一个字符串。

输出描述 Output Description

输出有n行，每行一个字符串，表示按对称系数从大到小排序后的字符串，对称系数相同时按字典序排序。

样例输入 Sample Input

5

pineapple

banana

peach

coconut

character

样例输出 Sample Output

banana

character

pineapple

coconut

peach

数据范围及提示 Data Size & Hint

数据范围：

1<=n<=100

1<=len<=500

1<=k<=len

提示：

对称系数k是指最长对称子序列的长度，非最长对称子串的长度。

分类标签 Tags 点此展开 

动态规划 单调性DP 字符串处理

所谓的字典序：就是ASCII码顺序，可以直接由strcmp比较出来

注意：c++除了0以外，正数负数都是真，!X只有x是0的时候才是真，其余时候都是假

思路一：将这个字符串反转，然后求两个字符串的最长公共子序列。

代码一：

#include< cstdio >

#include< iostream >

#include< cstring >

#include< algorithm >

using namespace std;

int dp[2333][2333];

struct str{

    string s;

    int len;

}l[2333];

bool cmp(str a,str b)

{

    if(a.len!=b.len) return a.len>b.len;

    return a.s

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int k=1;k<=n;k++)

    {

        cin>>l[k].s;

        string ss;

        memset(dp,0,sizeof(dp));

        int len=l[k].s.length();

        for(int i=len-1;i>=0;i--) ss+=l[k].s[i];

        for(int i=0;i

        {

            for(int j=0;j

            {

                if(l[k].s[i]==ss[j])

                    dp[i+1][j+1]=max(dp[i][j]+1,max(dp[i+1][j],dp[i][j+1]));

                else

                    dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);

            } 

        }

        l[k].len=dp[len][len];

    //  cout<<l[k].len<<endl;

    }

    sort(l+1,l+1+n,cmp);

    for(int i=1;i<=n;i++)

    {

        cout<<l[i].s<<endl;

    }

    return 0;

}

思路二：序列型DP，由小区间的对称长度扩展到大区间的最长对称

代码二：

#include< cstdio >

#include< cstring >

#include< iostream >

#include< algorithm >

using namespace std;

const int N=101;

const int LEN=501;

struct Dc{

char a[LEN];//dan ci

int k;//xi shu 

};

Dc dc[N];

int n,f[LEN][LEN];

void input()

{

scanf("%d",&n);

for(int i=1;i<=n;++i)

scanf("%s",dc[i].a+1);

}

void DP()

{

for(int l=1;l<=n;++l)

{

memset(f,0,sizeof(f));

int len=strlen(dc[l].a+1);

for(int i=1;i<=len;++i)

f[i][i]=1;

for(int i=len-1;i>=1;--i)

 for(int j=i+1;j<=len;++j)

 {

  if(dc[l].a[i]==dc[l].a[j]&&j==i+1) 

{

f[i][j]=2;

continue;//防止语句再走else语句 

}

  if(dc[l].a[i]==dc[l].a[j]&&j>i+1) 

f[i][j]=max(max(f[i+1][j],f[i+1][j-1]+2),f[i][j-1]);

  else f[i][j]=max(f[i+1][j],f[i][j-1]);

 }

dc[l].k=f[1][len];

//cout<<f[1][len]<<endl;

}

}

int cmp(const struct Dc &b,const struct Dc &c)

{

if((b.k>c.k)||(b.k==c.k&&strcmp(b.a+1,c.a+1)<0)) return 1;//注意只有＜0也是真 

return 0;

}

int main()

{

input();

DP();

sort(dc+1,dc+n+1,cmp);

for(int i=1;i<=n-1;++i)

printf("%s ",dc[i].a+1);

printf("%s",dc[n].a+1);

return 0;

}