Codeforces 585D Lizard Era: Beginning

很容易想到可以对于每个任务选不去的那一个人进行搜索，时间复杂度 \(O(3^n)\)，明显过不了。
发现 \(n\le 25,\lceil \frac{n}{2}\rceil\le 13\)，且各个任务间不会互相影响，便可以用折半搜索分成 \(2\) 部分来搜最后来合并。

考虑如何合并两部分，令前一部分得到的值分别为 \(a, b, c\)，后一部分得到的值分别为 \(a', b', c'\)，若合法则有 \(a + a' = b + b' = c + c'\)。
做差得到新的等式 \(a - b = b' - a', a - c = c' - a'\)，则可以后半部分以 \((b' - a', c' - a')\) 来查找前半部分中的 \((a - b, a - c)\)，记录一下 \(2\) 个部分的 \(a,a'\)，求和即可。
对于方案输出，搜索时记录一下不选的数得出剩下选的数即可。

时间复杂度 \(O(3^{\lfloor \frac{n}{2}\rfloor}\log_2 3^{\lceil \frac{n}{2}\rceil})\)。

// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: D. Lizard Era: Beginning
// Contest: Codeforces - Codeforces Round 325 (Div. 1)
// URL: https://codeforces.com/problemset/problem/585/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
int n, mid;
int val[N][3];
map<pair<int, int>, pair<int, int> > mp;
int ans[N];
void dfs1(int w, int a, int b, int c, int s) {
	if (w > mid) {
		if (! mp.count({a - b, a - c})) {
			mp[{a - b, a - c}] = {a, s};
		}
		else if (a > mp[{a - b, a - c}].first) {
			mp[{a - b, a - c}] = {a, s};
		}
		return ;
	}
	dfs1(w + 1, a + val[w][0], b + val[w][1], c, s * 3 + 2);
	dfs1(w + 1, a + val[w][0], b, c + val[w][2], s * 3 + 1);
	dfs1(w + 1, a, b + val[w][1], c + val[w][2], s * 3 + 0);
	return ;
}
int p1, p2, pmax = INT_MIN;
void dfs2(int w, int a, int b, int c, int s) {
	if (w > n) {
		if (mp.count({b - a, c - a})) {
			if (mp[{b - a, c - a}].first + a > pmax) {
				pmax = mp[{b - a, c - a}].first + a, p1 = mp[{b - a, c - a}].second, p2 = s;
			}
		}
		return ;
	}
	dfs2(w + 1, a + val[w][0], b + val[w][1], c, s * 3 + 2);
	dfs2(w + 1, a + val[w][0], b, c + val[w][2], s * 3 + 1);
	dfs2(w + 1, a, b + val[w][1], c + val[w][2], s * 3 + 0);
	return ;
}
int main() {
	scanf("%d", &n);
	mid = (1 + n) >> 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			scanf("%d", &val[i][j]);
		}
	}
	dfs1(1, 0, 0, 0, 0);
	dfs2(mid + 1, 0, 0, 0, 0);
	if (pmax != INT_MIN) {
		for (int i = mid; i; i--) {
			ans[i] = p1 % 3, p1 /= 3;
		}
		for (int i = n; i > mid; i--) {
			ans[i] = p2 % 3, p2 /= 3;
		}
		for (int i = 1; i <= n; i++) {
			if (ans[i] != 0) {
				printf("L");
			}
			if (ans[i] != 1) {
				printf("M");
			}
			if (ans[i] != 2) {
				printf("W");
			}
			printf("\n");
		}
	}
	else {
		printf("Impossible");
	}
	return 0;
}