zoj3777 Problem Arrangement(状态压缩dp)

ゝ一世哀愁。 2022-08-26 15:21 133阅读 0赞

题目链接：[http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3777][http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemCode_3777]

题意：给出n道题目以及每一道题目不同时间做的兴趣值，让你求出所有做题顺序中兴趣值不小于m的比例。按一个分数表示。

分析：首先想到的肯定是深搜，深搜枚举一个全排列，然后同时求和，看和大于等于m有多少种，输出结果，但是n的范围是（0--12）12！不能满足深搜的时间限

制，所以在比赛的时候华丽的超时了。

后面，想到了用dp来做，用dp【i】【j】来表示做了 i 道题目的趣味值为 j 的个数。那么可以用dp【i】【k+a【x】【i】】+=dp【i-1】【k】;但是发现其中的 x 是一个

不好控制的量，x表示从之前没有取过的行里面的所有行，但是怎么表示一个行有没有取过呢。。。是一个难题！！！想到用vector，但是发现它每次还是转移的，那

么我们是不是可以转移呢，但是发现转移后他有可能不只表示一种的，卡到这儿写不下去。

其实是个状态压缩dp，状态压缩就是把一些状态较少的情况用二进制的1表示出现0表示没有出现来表示，这样不仅表示方便快速，转移也方便

前面不能表示的状态我们可以用一个状态压缩dp来表示，///dp\[i\]\[j\]表示取i的二进制位为1的值兴趣值为j时的个数

那么我们就可以转移了。dp\[i+(1<<(j-1))\]\[k+a\[tmp+1\]\[j\]\] += dp\[i\]\[k\];

代码：

#include <cstdio>
    #include <cstring>
    const int N = 13;
    int dp[1<<13][510];   ///dp[i][j]表示取i的二进制位值兴趣值为j时的个数
    int f[N];   ///所有可能情况
    int a[N][N];
    
    void isit()
    {
        f[1]=1;
        for(int i=2;i<N;i++)
            f[i]=f[i-1]*i;
    }
    int gcd(int a,int b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    int main()
    {
        int T,m,n;
        scanf("%d",&T);
        isit();
        while(T--)
        {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    scanf("%d",&a[i][j]);
            memset(dp,0,sizeof(dp));
            dp[0][0]=1;
            for(int i=0;i<=(1<<n);i++)   ///二进制能表示的情况
            {
                int tmp=0;   ///表示已经表示过的题数
                for(int j=1;j<=n;j++)
                    if(i&(1<<(j-1)))
                        tmp++;
                //printf("%d\n",tmp);
                for(int j=1;j<=n;j++)
                {
                    if(i&(1<<(j-1))) continue;
                    for(int k=0;k<=m;k++)
                    {
                        if(k + a[tmp+1][j] >= m)   ///把大于值得全部保存到j
                            dp[i+(1<<(j-1))][m] += dp[i][k];
                        else
                            dp[i+(1<<(j-1))][k+a[tmp+1][j]] += dp[i][k];
                    }
                }
            }
            if(dp[(1<<n)-1][m] == 0)
                printf("No solution\n");
            else
            {
                int tm = gcd(f[n],dp[(1<<n)-1][m]);
                printf("%d/%d\n",f[n]/tm, dp[(1<<n)-1][m]/tm);
            }
        }
    }

搜索超时代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <stack>
    #include <string.h>
    using namespace std;
    
    int map[20][20];
    bool flag[20];
    
    int n,m,ans;
    
    void dfs(int p,int sum)
    {
        if(p == n)
        {
            if(sum >= m)
                ans ++;
            return ;
        }
        for(int i = 0; i < n; ++ i)
        {
            if(flag[i] == 0)
            {
                flag[i] = 1;
                dfs(p+1,sum+map[i][p]);
                flag[i] = 0;
            }
        }
    }
    
    int xxx(int x)
    {
        int ans = 1;
        for(int i = 2; i <= x; ++ i)
            ans *= i;
        return ans;
    }
    
    int gcd(int a,int b)
    {
        if(a<b)
            swap(a,b);
        while(b)
        {
            int temp = a%b;
            a=b;
            b=temp;
        }
        return a;
    }
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while(t--)
        {
            ans = 0;
            memset(flag,0,sizeof(flag));
            scanf("%d %d",&n,&m);
            for(int i = 0; i < n; ++ i)
                for(int j = 0; j < n; ++ j)
                    scanf("%d",&map[i][j]);
            dfs(0,0);
            if(ans == 0)
                puts("No solution");
            else
            {
                int ta=xxx(n);
                int g=gcd(ta,ans);
                ta /= g;
                ans /= g;
                printf("%d/%d\n",ta,ans);
            }
        }
        return 0;
    }

[http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemCode_3777]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3777