Codeforces #508 Div2 E. Maximum Matching

割と雑にやって通ってしまった。
http://codeforces.com/contest/1038/problem/E

問題

N個のブロックがあり、両端はそれぞれ4色のいずれかである。
また、ブロックにはスコアが付いている。

N個中いくつかのブロックを並べ、そのスコアの総和を最大化せよ。
ただし、ブロックを並べる際隣接するブロック同士は隣接面の色が一致しなければならない。
なお、ブロックの向きは反転できる。

解法

両端が異なるブロックは２個使えば両端の色が揃う。
よって、そのようなブロック群は、ブロック列中に両端のいずれかの色が１か所でも登場すればいくらでもはさみこめる。

そこで、任意の色をはじめとしてブロック列をDFSの要領で追加していくが、挟み込めるチャンスがあればブロック対をできるだけどんどん挟み込んでいこう。
そうすると挟み込みを除けば、各色のブロックの使用回数は極めて少なくなるのでDFSでもTLEしなくなる。

int N;
vector<int> V[16];
ll ma;
map<vector<int>,int> memo[4];

int ID(int x,int y) {
	if(x>y) swap(x,y);
	return x*4+y;
}

ll dfs(int cur,vector<int> C) {
	if(memo[cur].count(C)) return memo[cur][C];
	int i;
	ll ret=0;
	FOR(i,4) {
		int id=ID(cur,i);
		if(i==cur) {
			while(C[id]>=0) ret+=V[id][C[id]--];
		}
		else {
			while(C[id]>2) ret+=V[id][C[id]--]+V[id][C[id]--];
		}
	}
	ll ma=ret;
	FOR(i,4) {
		int id=ID(cur,i);
		if(C[id]>=0) {
			C[id]--;
			ma=max(ma,ret+V[id][C[id]+1]+dfs(i,C));
			C[id]++;
		}
	}
	
	return memo[cur][C]=ma;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>r>>y;
		x--,y--;
		if(x>y) swap(x,y);
		V[x*4+y].push_back(r);
	}
	
	vector<int> cand(16);
	FOR(x,4) FOR(y,4) {
		sort(ALL(V[x*4+y]));
		cand[x*4+y]=(int)V[x*4+y].size()-1;
	}
	
	FOR(i,4) ma=max(ma,dfs(i,cand));
	
	
	cout<<ma<<endl;
	
}

まとめ

もうちょっとうまくやらないといけないかなと思ったけどすんなり通った。