首页 > ACM题库 > HDU-杭电 > HDU 3091-Necklace-动态规划-[解题报告]HOJ
2014
03-01

HDU 3091-Necklace-动态规划-[解题报告]HOJ

Necklace

问题描述 :

One day , Partychen gets several beads , he wants to make these beads a necklace . But not every beads can link to each other, every bead should link to some particular bead(s). Now , Partychen wants to know how many kinds of necklace he can make.

输入:

It consists of multi-case .
Every case start with two integers N,M ( 1<=N<=18,M<=N*N )
The followed M lines contains two integers a,b ( 1<=a,b<=N ) which means the ath bead and the bth bead are able to be linked.

输出:

It consists of multi-case .
Every case start with two integers N,M ( 1<=N<=18,M<=N*N )
The followed M lines contains two integers a,b ( 1<=a,b<=N ) which means the ath bead and the bth bead are able to be linked.

样例输入:

3 3
1 2
1 3
2 3

样例输出:

2

一开始想到2^n*n^2算法,感觉肯定会超时,纠结半天之后没办法,去百度才发现大家都是这复杂度,然后兴致匆匆开始敲,敲完之后wrong了,再接再厉调了一下再交,结果给我几个TML,我就郁闷啦,为什么RP这么低,只好再优化一下,把每个状态的1用数组存起来,交上去还是wrong,想了想似乎会超int,改成int64再交就过了,前后搞了一个多小时,真心郁闷啊,说实话感觉像水过去的Necklace

ACcode:

#include<cstdio>
#include<cstring>
typedef long long LL;
const int NS=19;

int n,m;
int g[NS][NS],b[NS+1];
LL dp[1<<NS][NS];
int bit[1<<NS][NS];

void prepare()
{
    b[0]=1;
    for (int i=1;i<=NS;i++)
    b[i]=b[i-1]*2;

    int t,lim=1<<NS;
    for (int i=0;i<lim;i++)
    {
        t=0;
        for (int j=0;j<NS;j++)
        if (i&b[j]) bit[i][++t]=j;
        bit[i][0]=t;
    }
}

int main()
{
    prepare();
    int x,y;
    while (~scanf("%d%d",&n,&m))
    {
        for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
        g[i][j]=0;
        for (int i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            --x,--y;
            g[x][y]++,g[y][x]++;
        }

        int t,lim=1<<n;
        for (int i=0;i<lim;i++)
        for (int j=0;j<n;j++)
        dp[i][j]=0;
        for (int i=0;i<n;i++)
        dp[b[i]][i]=g[0][i];

        for (int i=1;i<lim;i++)
        for (int j=1;j<=bit[i][0]&&bit[i][j]<n;j++)
        {
            x=bit[i][j],y=i-b[x];
            for (int k=1;k<=bit[y][0]&&bit[y][k]<n;k++)
            {
                t=bit[y][k];
                if (g[t][x]==0) continue;
                dp[i][x]+=dp[y][t]*g[t][x];
            }
        }
        printf("%I64d\n",dp[lim-1][0]);
    }
    return 0;
}

参考:http://blog.csdn.net/cxsmile/article/details/9080029