Poj Solution 2557

http://poj.org/problem?id=2557

#include<iostream>
#include"string.h"
using namespace std;
int width[210],n;
int ans[210][210];
char fold[210];
bool init()
{
    int i,j;
    cin>>fold;
    if(cin.fail())return 0;
    n=strlen(fold);    
    for(i=0;i<n;i++)
    {
        for(j=1;i+j<n&&i-j>=0&&fold[i+j]+fold[i-j]=='A'+'V';j++)
            ;
        width[i]=j;
    }
    return 1;
}
inline int get_ans(int a,int b)
{
    return (a>b)?0:ans[a][b];
}
void doit()
{
    int i,j,k,t,s1,s2,l;    
    for(i=0;i<n;i++)
    ans[i][i]=1;
    for(l=1;l<n;l++)
    for(i=0;i+l<n;i++)
    {
        j=i+l;
        ans[i][j]=9999;
        for(k=i;k<=j;k++)
        if( ( j-k<k-i ? j-k:k-i ) < width[k] )
        {
            s1 = get_ans(i,k-1);
            s2 = get_ans(k+1,j);
            t= 1+( s1 > s2 ? s1:s2 );            
            if(t<ans[i][j])ans[i][j]=t;
        }
    }
}
int main()
{
    while(init())
    {
        doit();
        cout<<ans[0][n-1]<<endl;
    }
    return 0;
}    
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *