1812.txt

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

Source

Problem Id:1812  User Id:fzk 
Memory:24K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <queue>
#include <vector>
#include <memory.h>
#include <algorithm>

using namespace std;

char op[10];
int opn, ans;

void search( int h, const int *str, int len ) {
	int i, j, k;

	if( h >= ans )
		return;	

	if( len == 0 ) {
		ans = h;
		return;
	}

	if( h == opn )
		return;

	int w[20];
	
	for( i=0; i<len; i++ ) {
		if( (str[i]&255) == op[h] ) {
			memcpy( w, str, len*sizeof(int) );
			w[i] += (1<<8);
			if( (w[i]>>8) >= 3 ) {
				for( j=i-1, k=i+1; j>=0 && k<len && (w[j]&255)==(w[k]&255); j--, k++ ) {
					w[j] += (w[k]>>8<<8);
					if( (w[j]>>8) < 3 ) {
						k++;
						break;
					}
				}
				while( k<len )
					w[++j] = w[k++];
				search( h+1, w, j+1 );
			}
			else
				search( h+1, w, len );
		}
	}

}

int main( ) {
	int t, len, i;
	char w[21];
	int str[20], l;

	scanf( "%d", &t );

	while( t-- ) {
		scanf( "%d%d", &len, &opn );
		scanf( "%s", w );

		for( l=0, i=0; i<len; i++ ) {
			if( !i || w[i] != w[i-1] )
				str[l++] = (1<<8) | w[i];
			else
				str[l-1] += (1<<8);
		}
		ans = 6;
		
		scanf( "%s", op );
		sort( op, op+opn );

		do {
			search( 0, str, l );
		} while( next_permutation( op, op+opn ) );

		if( ans == 6 )
			printf( "lose\n" );
		else
			printf( "%d\n", ans );
	}
	return 0;
}