1393.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1393 on 2006-01-19 at 23:02:40 */ 
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

const int MAX = 10;
const int LIMIT = 102400;

bool bundle[3][MAX][MAX][MAX][4];
char e[LIMIT];
int minBund[LIMIT], minStop[LIMIT], lastStop[LIMIT];
int dep[LIMIT];

void bund(int, int);
bool good(int, int, int, int);

int main()
{
	int n, m;
	int i, j, k, t, T;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		scanf("%d %d", &n, &m);
		memset(bundle, false, sizeof(bundle));
		for(i = 0; i < n; i++) {
			int sp; char t[4];
			scanf("%s %d", t, &sp);
			for(j = 0; j < 3; j++) t[j] -= 'A';
			bundle[2][t[0]][t[1]][t[2]][sp+1] = true;
			switch(sp) {
			case 0:
				bundle[2][t[0]][t[1]][t[2]][0] = true;
				for(j = 0; j < 3; j++) {
					bundle[0][t[j]][0][0][0] = bundle[0][t[j]][0][0][1] = true;
					for(k = j+1; k < 3; k++)
						bundle[1][t[j]][t[k]][0][0] = bundle[1][t[j]][t[k]][0][1] = true;
				}
			break;
			case 1:
				bundle[1][t[0]][t[1]][0][2] = true;
				bundle[1][t[0]][t[2]][0][2] = true;
				bundle[1][t[1]][t[2]][0][1] = true;
				bundle[0][t[0]][0][0][2] = true;
				bundle[0][t[1]][0][0][1] = true;
				bundle[0][t[2]][0][0][1] = true;
			break;
			case 2:
				bundle[1][t[0]][t[1]][0][3] = true;
				bundle[1][t[0]][t[2]][0][2] = true;
				bundle[1][t[1]][t[2]][0][2] = true;
				bundle[0][t[0]][0][0][2] = true;
				bundle[0][t[1]][0][0][2] = true;
				bundle[0][t[2]][0][0][1] = true;
			break;
			}
		}
		minBund[0] = minStop[0] = lastStop[0] = 0;
		for(i = 1; i <= m; i++) {
			scanf("\n%c %d", &e[i], &dep[i]); e[i] -= 'A';
			minBund[i] = LIMIT;
			for(j = 0; j < 3 && j < i; j++) bund(i, j);
		}
		printf("%d %d\n", minBund[m], minStop[m]);
	}
	
	return 0;
}

void bund(int in2, int len)
{
	int in1 = in2 - len;
	if(len == 2 && dep[in2] == in2-1 && dep[in2-1] == in1) return;
	else {
		int i, usedStop = 0, pos = lastStop[in1-1], t[3] = { 0 };
		for(i = 0; i <= len; i++) t[i] = e[in1+i];
		bool *bun = bundle[len][t[0]][t[1]][t[2]];
		int k = min(len+2, 3);
		if(!(bun[0] && good(in1, len, LIMIT, pos))) {
			bool exe = false; int m = 0;
			for(usedStop = 1; usedStop < 3; usedStop++) {
				if(usedStop == 2) m = 1, pos = in1-1;
				for(i = k; i > m; i--)
					if(bun[i] && good(in1, len, i, pos)) {
						exe = true; pos = in1+i-2; break;
					}
				if(exe) break;
			}
		}
		if(usedStop == 3) return;
		in1--;
		if(minBund[in2] > minBund[in1]+1 || 
			(minBund[in2] == minBund[in1]+1 && minStop[in2] > minStop[in1]+usedStop) ||
			(minBund[in2] == minBund[in1]+1 && minStop[in2] == minStop[in1]+usedStop && lastStop[in2] < pos))
			minBund[in2] = minBund[in1]+1, minStop[in2] = minStop[in1]+usedStop, lastStop[in2] = pos;
	}
}
bool good(int b, int len, int p, int pos)
{
	int i, lmt = b+p-2;
	for(i = 0; i <= len; i++) {
		if(i >= p-1 && dep[b+i] > lmt) return false;
		if(i < p-1 && dep[b+i] > pos) return false;
	}
	return true;
}