2156.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2156 on 2006-01-28 at 16:02:14 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 128;
const int S_MAX = 32;

inline bool haveBit(int, int);

int main()
{
	int n, k, i, j, s, t;
	int pile[MAX], count[MAX], sum[MAX], move[MAX][5][S_MAX];

	while(scanf("%d %d", &n, &k) != EOF && n != 0) {
		int pn = -1; k = 1 << k;
		for(i = 0; i < n; i++) {
			scanf("%d", &pile[i]); pile[i]--;
			if(i == 0 || pile[i] != pile[i-1]) pile[++pn] = pile[i], count[pn] = 1;
			else count[pn]++;
		}
		for(i = 0; i < 5; i++) 
			for(j = 0; j < k; j++) move[0][i][j] = MAX;
		for(sum[0] = count[0], i = 1; i <= pn; i++) sum[i] = sum[i-1] + count[i];
		move[0][pile[0]][1<<pile[0]] = 0;
		for(i = 1; i <= pn; i++)
			for(j = 0; j < 5; j++)
				for(s = 0; s < k; s++) {
					move[i][j][s] = MAX;
					if(!haveBit(s, j)) continue;
					else if(j == pile[i]) {
						move[i][j][s] = move[i-1][j][s];
						int st = s ^ (1 << j);
						if(st == 0) move[i][j][s] = min(move[i][j][s], sum[i-1]);
						for(t = 0; t < 5; t++)
							if(haveBit(st, t)) move[i][j][s] = min(move[i][j][s], move[i-1][t][st]);
					} else move[i][j][s] = move[i-1][j][s]+count[i];
				}
		int best = MAX;
		for(i = 0; i < 5; i++)
			for(j = 0; j < k; j++) best = min(best, move[pn][i][j]);
		printf("%d\n", best);
	}
	
	return 0;
}

inline bool haveBit(int st, int bit)
{
	return (st & (1 << bit)) != 0;
}