2409.cpp

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

/* This Code is Submitted by wywcgs for Problem 2409 on 2006-10-25 at 20:03:41 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int S = 1 << 8;
const int CN = 128;
const char COLOR[] = "yrgb";
const int INF = 1 << 20;

pii fix(int, int, int);

int main()
{
	int T, card[CN], cdn[CN], d[CN][S];
	
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		memset(card, 0, sizeof(card)); memset(cdn, 0, sizeof(cdn));
		int n, lmt = -1; scanf("%d", &n);
		for(int i = 0; i < n; i++) {
			int p; char c; scanf("%d\n%c", &p, &c);
			for(int j = 0; j < 4; j++)
				if(COLOR[j] == c) { card[p] |= 1 << j; }
			cdn[p]++; lmt >?= p;
		}
		for(int i = 0; i < S; i++) d[0][i] = -INF;
		d[0][0] = 0;
		for(int i = 0; i < lmt; i++) {
			for(int j = 0; j < S; j++) d[i+1][j] = -INF;
			for(int j = 0; j < S; j++) {
				if(d[i][j] < 0)  continue;
				if(cdn[i+1] == 3) d[i+1][0] >?= d[i][j]+3*(i+1);
				else if(cdn[i+1] == 4) {
					d[i+1][0] >?= d[i][j]+4*(i+1);
					for(int k = 0; k < 4; k++) {
						pii st = fix(j, 1<<k, i+1);
						d[i+1][st.first] >?= d[i][j]+3*(i+1)+st.second;
					}
				}
				pii st = fix(j, card[i+1], i+1);
				d[i+1][st.first] >?= d[i][j]+st.second;
			}
		}
		int best = -INF;
		for(int j = 0; j < S; j++) best >?= d[lmt][j];
		printf("%d\n", best);
	}
	
	return 0;
}

pii fix(int ost, int cs, int p)
{
	int m[4], gp = 0;
	for(int i = 0; i < 4; i++) m[i] = (ost>>(i<<1))&3;
	for(int i = 0; i < 4; i++) {
		if(!(cs&(1<<i))) { m[i] = 0; continue; }
		if(m[i] == 3) gp += p;
		else if(m[i] == 2) { gp += 3*(p-1); m[i]++; }
		else m[i]++;
	}
	int nst = 0;
	for(int i = 0; i < 4; i++) nst |= m[i] << (i<<1);
	return pii(nst, gp);
}