某島

… : "…アッカリ~ン . .. . " .. .
February 20, 2013

SRM 571

Brief description:

… 點權最大團。。要求點數至少是 2/3 * n。。

Analysis:

… 比賽時覺得用最大團模板可以秒。。於是加了最優剪枝就交了。。(。TLE 。。
。。賽後 CLJ 在群裡面討論了一下她的做法。。大概是:。。

Yuuka Kazami(12xxxxxxxx) 1:59:37
我的做法是這樣的。。
兩個點沒有邊。。
枚舉哪個不在團里。
那麼每次少一個點。。。

http://community.topcoder.com/stat?c=problem_solution&rm=316166&rd=15491&pm=11705&cr=22840511

//}/* .................................................................................................................................. */

const int N = 60;

int s[N], w[N]; bool G[N][N];
int _sz, n, res;

void dfs(int a = 0, int b = 0, int c = n - _sz + 1, int ww = w[0] + s[0], LL bad = 0){
    if (!c || ww < res) return;

    if (a == n) res = ww;
    else if (a == b) dfs(a+1, 0, c, ww, bad);
    else {
        if (G[a][b] || _1(bad, a) ||_1(bad, b)) dfs(a, b+1, c, ww, bad);
        else {
            dfs(a, b+1, c-1, ww-w[a], bad|_1(a));
            dfs(a, b+1, c-1, ww-w[b], bad|_1(b));
        }
    }
}

class MagicMolecule {
public:
	int maxMagicPower(vector <int> magicPower, vector <string> magicBond) {

        REP_C(i, n = SZ(magicPower)) w[i] = magicPower[i];
        s[n-1] = 0; DWN(i, n, 0) s[i] = s[i+1] + w[i+1];

        _sz = ceil(2*n, 3); REP_2(i, j, n, n) G[i][j] = magicBond[i][j] == 'Y';
        res = -1, dfs();
        return res;
	}
};

複雜度有待分析?。
。。。和原題相比。。只增加了規模的限制條件。。在存在大量不合法的搜索分治時。。會極大的限制最優剪枝的發揮。。。
。。而這種搜索方法則很妥善的利用了這個信息。。

External link:

http://community.topcoder.com/stat?c=coder_room_stats&rd=15491&cr=22727863