http://poj.org/problem?id=2441

注意利用滚动数组。

if ((j & (1 << like[i][k])) == 0) /// 可以分配
 dp[now][j | (1 << like[i][k])] += dp[pre][j];
/*407ms,8400KB*/

const int mx = 20;

int like[mx][mx + 1], dp[2][1 << mx];

int f(int n, int m)
{
    int i, j, k, pre, now;
    dp[0][0] = 1;
    For(i, n)
    {
        pre = i & 1, now = pre ^ 1;
        mem(dp[now], 0); ///滚动数组
     For(j, 1 << m)
            if (dp[pre][j]) ///小优化
                Forr(k, 1, like[i][0] + 1)
                    if ((j & (1 << like[i][k])) == 0) /// 可以分配
                        dp[now][j | (1 << like[i][k])] += dp[pre][j];
    }
    return Acc(dp[now], 1 << m); ///就算全部分配了也会有不同的分配方案,故累加数组内的全部元素
}

int main()
{
    int n, m, i, j;
    while (~SII(n, m))
    {
        For(i, n)
        {
            SI(like[i][0]);
            Forr(j, 1, like[i][0] + 1) SI(like[i][j]), --like[i][j];
        }
        PI(f(n, m));
    }
    return 0;
}

Comments

comments powered by Disqus