The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

浙大A题 我无语了。。。

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[1<<16];


int main()
{

    int n,m;
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,0,sizeof(int)*(1<<n));
        int num;
        for(i=1;i<=m;i++)
        {
            scanf("%d",&num);
            int t=0;
            int k;
            for(j=1;j<=num;j++)
            {
                scanf("%d",&k);
                t|=(1<<(k-1));
            }
            dp[t]=1;
        }
        int res=0;
        int NN=(1<<n)-1;
        int x;
        for(i=1;i<=NN;i++)
        {
            x=i;
            while(x)
            {
                x=(x-1)&i;
                dp[i]=max(dp[i],dp[x]+dp[(~x)&(i)]);
            }
        }
        for(i=1;i<=NN;i++)
        {

            if(dp[i]>res)
                res=dp[i];
        }
        printf("%d\n",res);
    }
    return 0;
}

谢谢 我是智障 大牛的提示。

posted on 2010-03-15 14:32 abilitytao 阅读(175) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理