HDU 6149 Valley Numer II 状压DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6149

题意：中文题目

解法：状压DP，dp[i][j]代表前i个低点，当前高点状态为j的方案数，然后枚举转移就好了，我的代码里为什么要用滚动优化，内存？内存是足够的，不需要优化，我的dp表示是前i个低点所以转移不是从i-1转移，是从前一个低点转移，所以滚动数组能完美解决这个问题。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL mod = 1e9+7;

const int maxn = 1e4+10;

int T, n, m, K, h[maxn], a[maxn], g[50][50];

int dp[2][(1<<15)+10];

int main()

{

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d %d %d", &n,&m,&K);

        memset(h, 0, sizeof(h));

        memset(g, 0, sizeof(g));

        for(int i=1; i<=m; i++){

            int x,y;

            scanf("%d %d", &x,&y);

            g[x][y]=g[y][x]=1;

        }

        for(int i=0; i<K; i++){

            scanf("%d", &a[i]);

            h[a[i]] = 1;

        }

        int now = 0;

        memset(dp, 0, sizeof(dp));

        for(int i=1; i<=n; i++){

            if(h[i]) continue;

            now ^= 1;

            for(int j=0; j<(1<<K); j++) dp[now][j] = dp[now^1][j];

            for(int j=0; j<(1<<K); j++){

                for(int k=0; k<K; k++){

                    if(!(j&(1<<k))&&(g[i][a[k]])){

                        for(int k1=k+1; k1<K; k1++){

                            if(!(j&(1<<k1))&&(g[i][a[k1]])){

                                int news = (j)|(1<<k)|(1<<k1);

                                dp[now][news] = max(dp[now][news], dp[now^1][j]+1);

                            }

                        }

                    }

                }

            }

        }

        int ans = 0;

        for(int i=0; i<(1<<K); i++) ans = max(ans, dp[now][i]);

        printf("%d\n", ans);

    }

    return 0;

}