uva11584

将课本上所述方法实现即可，代码如下：

/*

 * Author:  Bingo

 * Created Time:  2015/1/25 23:49:49

 * File Name: uva11584.cpp

 */

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <time.h>

using namespace std;

const int maxint = -1u>>;

const int maxlen=;

int d[maxlen];

int s[maxlen][maxlen];

string st;

int work(){

    int len=st.size();

    memset(s,,sizeof(s));

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

        int p,q;

        s[i][i]=;

        //ji

        p=i-;q=i+;

        while (p>=&&q<len&&st[p]==st[q]){

            s[p][q]=;

            p--;q++;

        }

        //odd_left

        p=i-;q=i;

        while (p>=&&q<len&&st[p]==st[q]){

            s[p][q]=;

            p--;q++;

        }

        //odd_right

        p=i;q=i+;

        while (p>=&&q<len&&st[p]==st[q]){

            s[p][q]=;

            p--;q++;

        }

    }

}//s[i][j]是否为回文串

int main()

{

    int T;

    cin>>T;

    //string st;

    while (T--){

        cin>>st;

        work();

        int len=st.size();

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

            d[i]=;

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

            int j=;

            if (s[][i]) d[i]=;

            else

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

                if (s[j+][i]) d[i]=min(d[i],d[j]+);

            }

        }

        cout<<d[len-]<<endl;

    }

    return ;

}