# 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;
}

```
This entry was posted in poj. Bookmark the permalink.