程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ Problem Arrangement 遞推+狀壓

ZOJ Problem Arrangement 遞推+狀壓

編輯：C++入門知識

對於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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#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<= 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;
}