2930.txt

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

Problem Id:2930  User Id:fzk 
Memory:1792K  Time:888MS
Language:C++  Result:Accepted

Source 

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

#define count asdljflsdka
#define for_ii(k) for( ii[(k)]=0; ii[(k)]<m; ii[(k)]++ )

char a[20];
char w[110];

char e[6][4] = {
	 { 1, 2, 3, 4 },
	 { 0, 2, 4, 5 },
	 { 0, 1, 3, 5 },
	 { 0, 2, 4, 5 },
	 { 0, 1, 3, 5 },
	 { 1, 2, 3, 4 }
};

char num[20];
char answer[20];
int n, m;
int s[111][6];
bool flag[11][11][11][11][11][11];

void set( int a0, int a1, int a2, int a3, int a4, int a5 ) {
	flag[ a0 ][ a1 ][ a2 ][ a3 ][ a4 ][ a5 ] = true;
	flag[ a0 ][ a2 ][ a3 ][ a4 ][ a1 ][ a5 ] = true;
	flag[ a0 ][ a3 ][ a4 ][ a1 ][ a2 ][ a5 ] = true;
	flag[ a0 ][ a4 ][ a1 ][ a2 ][ a3 ][ a5 ] = true;
}

int clac() {
	int i, j, k, t, best = 0;
	for( i=0; i<6; i++ )
		s[0][i] = ( a[i] == w[0] );
		
	for( i=0; i<n-1; i++ )
	for( j=0; j<6; j++ )
	for( k=0; k<4; k++ )
	if( s[i+1][ e[j][k] ] < ( t = s[i][j] + ( a[ e[j][k] ] == w[i+1] ) ) )
		s[i+1][ e[j][k] ] = t;
	
	for( i=0; i<6; i++ )
		if( s[n-1][i] > best )
			best = s[n-1][i];
			
	return best;
}

int count[10];
int sign[10];

int main( ) {
	int i, ans, ii[6], h, c = 1;
	while( scanf( "%s", w ) == 1 ) {
		n = strlen( w );
		
		memset( count, 0, sizeof count );
		m = 0;
		
		for( i=0; i<n; i++ ) {
			w[i] -= '0';
			if( count[ w[i] ] == 0 )
				num[m++] = w[i];
			count[ w[i] ] ++;
		}
		
		ans = 0;
		if( count[ 0 ] == 0 )
			num[m++] = 0;
		sort( num, num+m );
		memset( flag, 0, sizeof flag );
				
		for_ii(0)for_ii(1)for_ii(2)for_ii(3)for_ii(4)for_ii(5) {
			
			memset( sign, 0, sizeof sign );
			h = 0;
			for( i=0; i<6; i++ ) {
				a[i] = num[ ii[i] ];
				if( !sign[ a[i] ] ) {
					h += count[ a[i] ];
					sign[ a[i] ] = true;
				}
			}
			if( h < ans ) continue;
			
			if( flag[ a[0] ][ a[1] ][ a[2] ][ a[3] ][ a[4] ][ a[5 ] ] )
				continue;
	 
			set( a[0], a[1], a[2], a[3], a[4], a[5] );
			set( a[5], a[1], a[2], a[3], a[4], a[0] );
			set( a[1], a[0], a[2], a[5], a[4], a[3] );
			set( a[3], a[0], a[2], a[5], a[4], a[1] );
			set( a[2], a[1], a[0], a[3], a[5], a[4] );
			set( a[4], a[1], a[0], a[3], a[5], a[2] );

			set( a[0], a[4], a[3], a[2], a[1], a[5] );
			set( a[5], a[4], a[3], a[2], a[1], a[0] );
			set( a[1], a[4], a[5], a[2], a[0], a[3] );
			set( a[3], a[4], a[5], a[2], a[0], a[1] );
			set( a[2], a[5], a[3], a[0], a[1], a[4] );
			set( a[4], a[5], a[3], a[0], a[1], a[2] );
			
			memset( s, 0, sizeof s );
			
			h = clac();
			
			if( h >= ans ) {
				sort( a, a+6 );
				if( h > ans || ( h==ans && std::lexicographical_compare(a, a+6, answer, answer+6)  ) ) {
					for( i=0; i<6; i++ )
						answer[i] = a[i];
				}
				ans = h;
			}
		}
		
		printf( "Dice %d: discrepancy is %d, digits used:", c++, n-ans );
		for( i=0; i<6; i++ )
			printf( " %d", int(answer[i]) );
		printf( "\n" );
	}
	return 0;
}