http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=848&page=show_problem&problem=1059

颜色只有 20 种,直接位压缩,记忆化搜索时把 mask 也传进去,若 __builtin_popcount(mask) == 5 则返回 0。

/*0.228s*/
const int mx = 41;

int color[4][mx], dp[mx][mx][mx][mx];

int f(int a, int b, int c, int d, int mask)
{
    if (__builtin_popcount(mask) == 5) return 0;
    int &DP = dp[a][b][c][d], cnt;
    if (~DP) return DP;
    DP = 0;
    if (a) cnt = (mask >> color[0][a]) & 1, Qmax(DP, cnt + f(a - 1, b, c, d, mask ^ (1 << color[0][a])));
    if (b) cnt = (mask >> color[1][b]) & 1, Qmax(DP, cnt + f(a, b - 1, c, d, mask ^ (1 << color[1][b])));
    if (c) cnt = (mask >> color[2][c]) & 1, Qmax(DP, cnt + f(a, b, c - 1, d, mask ^ (1 << color[2][c])));
    if (d) cnt = (mask >> color[3][d]) & 1, Qmax(DP, cnt + f(a, b, c, d - 1, mask ^ (1 << color[3][d])));
    return DP;
}

int main()
{
    int n, i, j;
    while (SI(n), n)
    {
        rForr(j, n, 1) For(i, 4) SI(color[i][j]);
        mem(dp, -1);
        PI(f(n, n, n, n, 0));
    }
    return 0;
}

Comments

comments powered by Disqus