#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define N 5001

int len;
char str[N];
short opt[N][N];

void dynamic()
{
    memset( opt, 0, sizeof(opt) );
    for( int i = 1; i <= len; i++ )
    opt[i][i] = 1;
    
    for( int r = 2; r <= len; r++ )
    {
        for( int i = 1; i <= len-r+1; i++ )
        {
                int j = r+i-1;
                opt[i][j] = opt[i+1][j] + 1;
                
                if( opt[i][j] > opt[i][j-1]+1 )  
                opt[i][j] = opt[i][j-1]+1;   
                int temp = 0;
                if( str[i] != str[j] )
                temp = 2;
                if( opt[i][j] > opt[i+1][j-1]+temp )
                {
                        opt[i][j] = opt[i+1][j-1]+temp;    
                }
        }    
    }    
    printf( "%d\n", opt[1][len] );
}

int main()
{
    scanf( "%d", &len );
    scanf( "%s", str+1 );
    dynamic();    
        
}

• Re:Why wa, not memory limit error? (492) anne2277 2005-06-30 10:55:32
  • Re:Why wa, not memory limit error? (60) anne2277 2005-06-30 11:20:48
    • Re:Why wa, not memory limit error? (98) anne2277 2005-06-30 12:10:00
  • Re:Why wa, not memory limit error? (224) hot 2005-11-27 14:00:32
    • ....... (234) frkstyc 2005-11-27 14:31:35
      • Re:....... (65) hot 2005-11-30 19:04:01
    • Please don't fish me... (71) ejkim7199 2006-07-09 13:38:03