uva 11584 动态规划

向右看齐 2022-08-03 13:41 7阅读 0赞

给定一串字符串，看最少能把它分成几个回文字符串。

SampleInput

racecar

fastcar

aaadbccb

SampleOutput

dp\[i\]=min(dp\[j\]+1);(i~j为回文)。开始一看数据是1000，没敢写，去网上看了看都是这样做的，只好也跟着这样做，本以为是O（n^3）的复杂度，现在看来可能系数很小，但是感觉也是不太明白，系数再小也是n^3啊，尽然78ms就跑完了，我都不敢相信自己的眼睛了，看来以后实在想不到解法可以考虑一下暴力。。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    char a[1111];
    int dp[1111];
    bool check(int l,int r)
    {
        while(l<r)
        {
            if(a[l++]!=a[r--])return 0;
        }
        //cout<<"i=="<<r<<" ";
        return 1;
    }
    
    int main()
    {
        int T=in();
        while(T--)
        {
            gets(a);
            int n=strlen(a);
            for(int i=0;i<n;i++)
            {
                dp[i]=dp[i-1]+1;   //初始化为上一个加一
                for(int j=0;j<=i;j++)
                {
                    if(check(j,i))
                    {
                        if(j>0)dp[i]=min(dp[j-1]+1,dp[i]);
                        else dp[i]=1;
                    }
    
                }
            }
            //for(int i=0;i<n;i++)
            cout<<dp[n-1]<<endl;
        }
        return 0;
    }