UVA 11584 Partitioning by Palindromes DP

제목 링크

n2의 예처리 i~j 메모 문자열

그리고 n2 DP

11584 Partitioning by Palindromes

Can you read upside-down? We say a sequence of characters is a palindrome if it is the same written forwards and backwards. For example, ‘racecar’ is a palindrome, but ‘fastcar’ is not. A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, (‘race’, ‘car’) is a partition of ‘racecar’ into two groups. Given a sequence of characters, we can always create a partition of these characters such that each group in the partition is a palindrome! Given this observation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palindrome? For example: • ‘racecar’ is already a palindrome, therefore it can be partitioned into one group. • ‘fastcar’ does not contain any non-trivial palindromes, so it must be partitioned as (‘f’, ‘a’, ‘s’, ‘t’, ‘c’, ‘a’, ‘r’). • ‘aaadbccb’ can be partitioned as (‘aaa’, ‘d’, ‘bccb’).

Input

Input begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within.

Output

For each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.Universidad de Valladolid OJ: 11584 – Partitioning by Palindromes 2/2

Sample Input

3 racecar fastcar aaadbccb

Sample Output

1 7 3

/* *********************************************** Author :CKboss Created Time :2015 02 09      12 32 31  File Name :UVA11584.cpp ************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

const int maxn=1111;

int n;
bool isP[maxn][maxn];
char str[maxn];
int dp[maxn];

void init()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            int left=i-j,right=i+j;
            if(left>=0&&right<n)
            {
                if(str[left]==str[right])
                    isP[left+1][right+1]=true;
                else break;
            }
            else break;
        }
    }
    for(int i=0;i<n-1;i++)
    {
        int left=i,right=i+1;
        if(str[left]==str[right])
        {
            for(int j=0;j<n;j++)
            {
                left=i-j;
                right=i+1+j;
                if(left>=0&&right<n) ;
                else break;
                if(str[left]==str[right])
                    isP[left+1][right+1]=true;
                else break;
            }
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);

    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        scanf("%s",str);
        n=strlen(str);
        memset(dp,63,sizeof(dp));
        memset(isP,0,sizeof(isP));
        init();
        dp[0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(isP[j+1][i]) 
                    dp[i]=min(dp[i],dp[j]+isP[j+1][i]);
            }
        }
        printf("%d
",dp[n]);
    }

    return 0;
}