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

Posted by xiaodao
Category: TopCoder