Write a programto determine the length of the longest palindrome you can get from a string.

Input and Output

The first line of input contains an integerT(≤ 60). Each of the nextTlines is a string, whose length is always less than 1000.

For ≥90% of the test cases, string length ≤ 255.

For each input string, your program should print the length of the longest palindrome you can get by removing zero or more characters from it.

Sample Input

2
ADAM
MADAM

Sample Output

3
5

---

Problemsetter: Raymond Chun

---------------

听说有空串，所以必须用gets()

---------------

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char s[1111];
int f[1111][1111];
int n;

int dfs(int l,int r)
{
    if (f[l][r]!=-1) return f[l][r];
    if (r-l<1) return 0;
    int ret=0;
    if (s[l]==s[r])
    {
        ret=dfs(l+1,r-1);
    }
    else
    {
        ret=min( dfs(l+1,r), dfs(l,r-1) )+1;
    }
    f[l][r]=ret;
    return ret;
}

int main()
{
    int T;
    scanf("%d",&T);
    getchar();
    while (T--)
    {
        memset(f,-1,sizeof(f));
        //scanf("%s",s+1);
        gets(s+1);
        n=strlen(s+1);
        int ans=dfs(1,n);
        printf("%d\n",n-ans);
    }
    return 0;
}

优质内容筛选与推荐>>
1、处理字符串函数整理
2、Heritrix 3.1.0 源码解析（二十九）
3、【BZOJ】1225: [HNOI2001] 求正整数
4、.net mvc笔记1_ The MVC Pattern
5、多线程编程学习九(并发工具类).

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中