UVa : 11584 (Partitioning by Palindromes)



// http://uva.onlinejudge.org/external/115/11584.html
// Runtime: 0.056s
// Tag: Dp, palindrome 

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on March 25, 2011, 10:19 AM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for ( int i = (a); i < (b); i++ )
#define Fors(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

char inp [1000 + 10];
int state [1000 + 10];

bool isPalindrome (int s, int t)
{
    while ( s < t ) {
        if ( inp [s] != inp [t] ) return false;
        s++;
        t--;
    }

    return true;
}

int main(int argc, char** argv) {
    int testCase; scanf ("%d", &testCase);

    while ( testCase-- ) {
        scanf ("%s", inp);
        int len = strlen (inp);

        for ( int i = 0; i < 1010; i++ ) state [i] = INF_MAX;

        state [0] = 0;
        state [1] = 1;

        for ( int i = 1; i < len; i++ ) {
            for ( int j = 0; j <= i; j++ ) {
                if ( isPalindrome (j, i) ) { 
                    state [i + 1] = min (state [i + 1], state [j] + 1);
                    
                }
            }
        }

        /*
        for ( int i = 0; i <= len; i++ )
            printf ("%d ", state [i]);
        */
        
        printf ("%d", state [len]);
        printf ("\n");
    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s