2938.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2938  User Id:fzk 
Memory:140K  Time:46MS
Language:C++  Result:Accepted

Source 

#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( "%d\n", need );
	}
	return 0;
}