HDU 3091(动态规划-状态压缩)

拼搏现实的明天。 2022-06-01 00:41 195阅读 0赞

问题描述:

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.

Input

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.

Output

An integer , which means the number of kinds that the necklace could be.

Sample Input

3 3
    1 2
    1 3
    2 3

Sample Output

题目题意:给我们n棵珠，给定它们的连接规则，问有多少种项链(注意首尾相连)

题目分析:因为珠子不多，所以我们可以用数字的每一位表示珠子的状态，因为珠子的连接是有规则的，不是所有的珠子都可以相连，假设我们如果知道了前一个珠子是那个，那么后面那些珠子可以相连就确定了，所以还需要一维来表示最后一颗珠子是谁。

dp\[i\]\[j\]的保存的就是在状态i下，结尾是珠子j的多少种情况。还有一点是首尾的问题，我们可以假设第一个是第一颗珠子，结果不影响，那么尾部那些就可以确定了。

代码如下:

#include<iostream>
    #include<cstring>
    #include<cmath>
    #include<cstdio>
    #define ll long long
    using namespace std;
    
    ll dp[(1<<18)][20];
    bool G[20][20];
    
    int main()
    {
        int n,m;
        while (scanf("%d%d",&n,&m)!=EOF) {
            memset (G,false,sizeof (G));
            for (int i=1;i<=m;i++) {
                int a,b;
                scanf("%d%d",&a,&b);
                G[a][b]=G[b][a]=true;//保存图
            }
            memset (dp,0,sizeof (dp));
            dp[1][1]=1;
            for (int i=0;i<=((1<<n)-1);i++) {
                for (int j=n;j>=1;j--) {
                    if (!dp[i][j]) continue;
                    for (int k=1;k<=n;k++) {
                        if (G[k][j]&&!(i&(1<<(k-1)))) dp[i|(1<<(k-1))][k]+=dp[i][j];
                    }
                }
            }
            ll ans=0;
            for (int i=1;i<=n;i++) {
                if (G[1][i])//首尾相连
                ans+=dp[((1<<n)-1)][i];
            }
            printf("%lld\n",ans);
        }
        return 0;
    }