UVA 11584 入门DP

一开始把它当成暴力来做了，即，从终点开始，枚举其最长的回文串，一旦是最长的，马上就ans++，再计算另外的部分。。。结果WA了

事实证明就是一个简单DP，算出两个两个点组成的线段是否为回文，再用LCS的类似做法得到每个子结构的最优值。

#include <cstdio>

#include <cstring>

#define N 1010

char s[N];

int n,len,d[N][N],sum[N];

int min(int a,int b)

{

    if (a<b) return a;

    return b;

}

int ok(int a,int b)

{

    for (int i=a,j=b;i<j;i++,j--)

    {

        if (s[i]!=s[j]) return ;

    }

    return ;

}

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%s",s);

        len=strlen(s);

        int k,q,ans=;

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

        {

            sum[i]=N;

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

            {

                d[j][i]=ok(j,i);

            }

        }

        sum[]=;

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

        {

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

            {

                //printf("%d %d %d\n",j,i,d[j][i]);

                if (d[j][i])

                {

                    int tmp;

                    if (j>)

                    {

                        tmp=+sum[j-];

                    }

                    else

                        tmp=;

                    sum[i]=min(sum[i],tmp);

                }

            }

        }

        printf("%d\n",sum[len-]);

    }

    return ;

}

巴特西

UVA 11584 入门DP

最新文章

热门文章