Poj Solution 2938

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

#include <algorithm>
#include <cstdio>
#include <string>
#include <map>
#include <stack>
#include <memory.h>
#include <math.h>
#include <queue>
using namespace std;

string str[1100];
int year[1100];
int ans[1100];


int doit( int l, int r ) {
    int i, j, b, e;
    ans[l] = 0;
    for( i=l+1; i<=r; i++ ) {
        ans[i] = 999999;
        for( j=l; j<i; j++ ) {
            if( year[i]>=year[j]+2 )
                continue;
            else if( year[i] == year[j] ) {
                if( ans[j]+1 < ans[i] )
                    ans[i] = ans[j]+1;
            }
            else {
                if( ans[j]+1 < ans[i] && str[j] >= str[i] )
                    ans[i] = ans[j]+1;
            }
        }
    }
    return ans[r];
}
                

int main( ) {
    int n, i, need, cur, l;
    char w[100], f[100];
    
    while( 1 ) {
        scanf( "%d", &n );
        if( n == 0 )
            break;
            
        cur = 0;
        l = -1;
        need = 0;
        
        for( i=0; i<n; i++ ) {
            scanf( "%s%*s%s", w, f );
            str[i] = w;
            
            if( i && str[i-1] >= str[i] )
                cur++;
            year[i] = cur;
            
            if( f[0] == '+' ) {
                if( l >= 0 )
                    need += doit( l, i );
                else
                    need++;
                l = i;
            }
        }
        
        if(l>=0 && year[l] != year[n-1] ) {
            str[n] = "";
            year[n] = year[n-1]+1;
            need += doit( l, n ) - 1;
        }
        
        printf( "%dn", need );
    }
    return 0;
}