51nod_1154 回文串的划分

说实话。。最开始看这题感觉一定好难。。。好高大上。。。我的马拉车还不熟。。。。这种。。但是本着做不出来也要至少看看的心态，吧个题看完了。。然后简单的想了想，好像是个挺直观的动态规划，因为看到数据几乎就像是得到了提示：ON2可以过哟，想想双重FOR循环吧~~这样诱人的声音。

但是后面我做完之后看着提。。。似乎我给写了个ON3的代码。。。居然还过了。。。。

定义DP[K]代表[0，K]内划分的子串的个数，状态转移为DP[J]=MIN(DP[K]+1(如果K,J是回文))。

#include<bits/stdc++.h>

using namespace std;

const long long INF=1e12+;

const long long MAXN=;

long long dp[MAXN];

char str[MAXN];

bool check(int pos1,int pos2)

{

    for(int i=pos1,j=pos2;i<=j;i++,j--)

    {

        if(str[i]!=str[j])return false;

    }return true;

}

int main()

{

    scanf("%s",(str+));

    int len=strlen(str+);

    dp[]=;

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

    {

        long  long ans=INF;

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

        {

            if(check(j,i))

            {

                ans=min(ans,dp[j-]+);

            }

        }

        dp[i]=ans;

    }

    cout<<dp[len];

    return ;

}

巴特西

51nod_1154 回文串的划分

最新文章

热门文章