学步园

思路：状态压缩DP，先说一下状态方程dp[i][j] 表示第i头牛在j的状态下的方法数 dp[i][j] =
sigma(dp[i-1][k] ) k 从0 到 1<<(m-1);
这里用到滚到数组 因为dp[20][1<<20]
的数组会MLE。

//8384K   
407MS
#include <stdio.h>
#include <string.h>
#define M 25

int dp[2][1<<20],a[M][M];//a[i][j] 为1
表示第i头牛能在第j列
int n,m;
int main ()
{
    int
i,j,k,t,p;
    while
(~scanf ("%d%d",&n,&m))
    {
       
memset (a,0,sizeof(a));
       
memset (dp,0,sizeof(dp));
       
dp[0][0] = 1;
       
for (i = 1; i <= n; i ++)
       
{
           
scanf ("%d",&t);
           
while ( t --)
           
{
               
scanf ("%d",&p);
               
a[i][p] = 1;
           
}
       
}
       
for (i = 1; i <= n; i ++)
       
{
           
for (j = 0; j <
(1<<m); j ++) 
//每种状态访问一次
               
if
(dp[1-i&1][j])      
//只有在前i-1头牛的j状态有值的情况下                     
才用确定在这种情况下第i头牛的放法
               
{
                   
for (k = 1; k <= m; k ++)