ZOJ Problem Arrangement 递推+状压

对于dp[ i ][ j ] , 设 i 的二进制中 1 的个数为 Si。

则dp[ i ][ j ]表示在前Si行中，选取 i 的二进制对应的列所能得到分数 j 的方案数。

则递推方程为:

dp[ t ][ k ] += dp[ i ][ j ]  ， Si +1 == St && （t 的二进制与 i 的二进制有且只有一位不一样，换言之，只能在Sl行选取未在前 Si 行选取的一个列）。

最后 dp[1<<(n-1)][m]即为可行方案总数，而总的方案数为 n！。

又因此为01分布，所以期望为 dp[1<<(n-1)][m]/(n!)，求出最大公约数化简即可。

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <map>

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long int
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 1000000007
#define LM(a,b) (((ULL)(a))<<(b))
#define RM(a,b) (((ULL)(a))>>(b))

const double PI = acos(-1.0);

using namespace std;

int p[14][14];

struct N
{
    LL ans,row;
}dp[4100][510];

LL gcd(LL a,LL b)
{
    if(b == 0)
        return a;
    return gcd(b,a%b);
}

LL mul[14];

int main()
{
    int T;

    int n,m,i,j,k,Max;

    for(mul[0] = 1,i = 1; i <= 12; ++i)
    {
        mul[i] = mul[i-1]*i;
    }

    scanf("%d",&T);

    while(T--)
    {
        scanf("%d %d",&n,&m);

        for(i = 1; i <= n; ++i)
        {
            for(j = 1; j <= n; ++j)
            {
                scanf("%d",&p[i][j]);
            }
        }

        Max = (1<<n)-1;

        for(i = 1; i <= Max; ++i)
        {
            memset(dp[i],0,sizeof(N)*(m+3));
        }

        for(i = 1; i <= n; ++i)
        {
            if(p[1][i] >= m)
            {
                dp[1<<(i-1)][m].ans++;
                dp[1<<(i-1)][m].row = 1;
            }
            else
            {
                dp[1<<(i-1)][p[1][i]].ans++;
                dp[1<<(i-1)][p[1][i]].row = 1;
            }
        }

        LL r;

        for(i = 1; i < Max; ++i)
        {
            for(j = 0; j <= m; ++j)
            {
                if(dp[i][j].ans)
                {
                    r = dp[i][j].row+1;

                    for(k = 1; k <= n; ++k)
                    {
                        if((i&(1<<(k-1))) == 0)
                        {
                            if(j+p[r][k] >= m)
                            {
                                dp[i+(1<<(k-1))][m].ans += dp[i][j].ans;
                                dp[i+(1<<(k-1))][m].row = r;
                            }
                            else
                            {
                                dp[i+(1<<(k-1))][j+p[r][k]].ans += dp[i][j].ans;
                                dp[i+(1<<(k-1))][j+p[r][k]].row = r;
                            }
                        }
                    }
                }

            }
        }

        if(dp[Max][m].ans)
        {
            LL temp = gcd(mul[n],dp[Max][m].ans);

            printf("%lld/%lld\n",mul[n]/temp,dp[Max][m].ans/temp);
        }
        else
        {
            printf("No solution\n");
        }
    }
    return 0;
}

ZOJ Problem Arrangement 递推+状压,布布扣,bubuko.com

ZOJ Problem Arrangement 递推+状压

原文：http://blog.csdn.net/zmx354/article/details/23618595