首页 > 代码库 > ZOJ-3777-Problem Arrangement(状态DP)

ZOJ-3777-Problem Arrangement(状态DP)

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3777

题意:

输入n和m,接下来一个n*n的矩阵,a[i][j]表示第i道题放在第j个顺序做可以加a[i][j]的分数,问做完n道题所得分数大于等于m的概率。用分数表示,分母为上述满足题意的方案数,分子是总的方案数,输出最简形式。

分析:

一开始用的DFS做的,复杂度太高,果断超时。。

正解是状压DP:

由于总的方案数为n! ,简化为求给一个n*n的矩阵,每一行每一列各选一个数使得n个数之和大于等于m的方案数。

n的范围是1 <= n <= 12,每一列选与不选分别用1和0表示,状态数最多达到1<<12。

dp[sta][score]表示状态为i得分为j的方案数。

sta通过二进制上1的位置来表示哪几列被选了。

在当前状态下,对于某一列j,若sta&(1<<j) == 0说明第j列还未选,继而可以由第j列来更新,否则说明第j列已经被选。

状态转移方程为:

  •                        dp[sta][g ] = sum(dp[i][g-a[ cnt+1][j]]);

    其中i当前状态的可行的上一状态,cnt为当前sta选到了第几行。

    由于从当前状态寻找上一状态很困难,所以我们反着来,用上一状态更新它可达的下一状态(具体看代码)

    最后dp[ (1<<n) -1 ][ m ]表示每行每列各取一个数,最后取n个数并得分大于等于m的方案数。(将动态转移方程变化了一下)

    说的不是很明白,代码写的很清楚。

    代码:

  • #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    
    int dp[1<<12][510];
    int f[13];
    int a[13][13];
    
    int gcd(int a, int b)
    {
        if(b == 0) return a;
        return gcd(b,a%b);
    }
    
    int main()
    {
        int test;
        int n,m;
    
        f[0] = 1;
        for(int i = 1; i <= 12; i++)
            f[i] = f[i-1] * i;
    
        scanf("%d",&test);
        while(test--)
        {
            scanf("%d %d",&n,&m);
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    scanf("%d",&a[i][j]);
    
            for(int i = 0; i < (1<<n); i++)
                for(int j = 0; j <= m; j++)
                    dp[i][j] = 0;
            dp[0][0] = 1;
    
            for(int i = 0; i < (1<<n); i++)
            {
                int cnt = 0;
                for(int j = 1; j <= n; j++)
                {
                    if(i & (1<<(j-1)) )
                        cnt++;
                }
    
                for(int j = 1; j <= n; j++)
                {
                    if(i & (1<<(j-1))) continue;
    
                    for(int g = 0; g <= m; g++)
                    {
                        if(g + a[cnt+1][j] >= m)
                            dp[i+(1<<(j-1))][m] += dp[i][g];
                        else
                            dp[i+(1<<(j-1))][g+a[cnt+1][j]] += dp[i][g];
                    }
                }
            }
            if(dp[(1<<n)-1][m] == 0)
                printf("No solution\n");
            else
            {
                int tmp = gcd(f[n],dp[(1<<n)-1][m]);
                printf("%d/%d\n",f[n]/tmp, dp[(1<<n)-1][m]/tmp);
            }
        }
    
        return 0;
    }

    ZOJ-3777-Problem Arrangement(状态DP)