Codeforces Round #325 (Div. 1) D. Lizard Era: Beginning

問題

codeforces.com

解法

半分全列挙するだけです。

覚えておく量は, 「L と M の差」, 「L と W の差」だけで十分です。

const int MAXN = 30;
const int INF = 1e9;
int Q[MAXN][3];
int n, N;

struct quests {
    vector<int> select;
    int L, M, W;
};
map<pii, quests> qs;

void print(const vector<int>& v) {
    for (int el : v) cout << el << "  ";
    cout << endl;
}

void dfs(int i, vector<int> qq, vector<int>& v) {
    if (i == N) {
        pii p(qq[0]-qq[1], qq[0]-qq[2]);
        if (qs.find(p) == qs.end() || qs[p].L < qq[0]) {
            quests q;
            q.select = v;
            q.L = qq[0];
            q.M = qq[1];
            q.W = qq[2];
            qs[p] = q;
        }
        return;
    }
    for (int j = 0; j < 3; j++) {
        v.push_back(j);
        for (int k = 0; k < 3; k++) if (k != j) qq[k] += Q[i][k];
        dfs(i+1, qq, v);
        for (int k = 0; k < 3; k++) if (k != j) qq[k] -= Q[i][k];
        v.pop_back();
    }
}

int ans = -INF;
vector<int> best;

void dfs2(int i, vector<int> qq, vector<int>& v) {
    if (i == n) {
        pii p(qq[1]-qq[0], qq[2]-qq[0]);
        if (qs.find(p) != qs.end()) {
            quests q = qs[p];
            int l = q.L + qq[0];
            if (ans < l) {
                ans = l;
                for (int j = 0; j < N; j++) {
                    best[j] = q.select[j];
                }
                for (int j = N; j < n; j++) {
                    best[j] = v[j-N];
                }
            }
        }
        return;
    }
    for (int j = 0; j < 3; j++) {
        v.push_back(j);
        for (int k = 0; k < 3; k++) if (k != j) qq[k] += Q[i][k];
        dfs2(i+1, qq, v);
        for (int k = 0; k < 3; k++) if (k != j) qq[k] -= Q[i][k];
        v.pop_back();
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> Q[i][0] >> Q[i][1] >> Q[i][2];
    }
    N = n/2;
    vector<int> v;
    dfs(0, vi(3), v);
    best.resize(n);
    dfs2(N, vi(3), v);
    if (ans == -INF) {
        cout << "Impossible" << endl;
        return 0;
    }
    for (int i = 0; i < n; i++) {
        switch(best[i]) {
            case 0:
                cout << "MW" << endl;
                break;
            case 1:
                cout << "LW" << endl;
                break;
            case 2:
                cout << "LM" << endl;
                break;
        }
    }
    return 0;
}