首页 > 代码库 > [ACM] hihoCoder 1075 开锁魔法III (动态规划,组合数学)

[ACM] hihoCoder 1075 开锁魔法III (动态规划,组合数学)

描述

一日,崔克茜来到小马镇表演魔法。

其中有一个节目是开锁咒:舞台上有 n 个盒子,每个盒子中有一把钥匙,对于每个盒子而言有且仅有一把钥匙能打开它。初始时,崔克茜将会随机地选择 k 个盒子用魔法将它们打开。崔克茜想知道最后所有盒子都被打开的概率,你能帮助她回答这个问题吗?

输入

第一行一个整数 T (T ≤ 100)表示数据组数。 对于每组数据,第一行有两个整数 n 和 k (1?≤?n?≤?300,?0?≤?k?≤?n)。 第二行有 n 个整数 ai,表示第 i 个盒子中,装有可以打开第 ai 个盒子的钥匙。

输出

对于每组询问,输出一行表示对应的答案。要求相对误差不超过四位小数。

样例输入
4
5 1
2 5 4 3 1
5 2
2 5 4 3 1
5 3
2 5 4 3 1
5 4
2 5 4 3 1
样例输出
0.000000000
0.600000000
0.900000000
1.000000000


解题思路:

做这种题真是头疼,没思路无从下手,还是做的题少再加上没有仔细得分析,下面就来好好得分析一下本题。

1.只要打开一个盒子,那么就能打开一连串的盒子,因为打开的盒子里面有着另一个盒子的钥匙。

2.要求全部盒子打开的概率,那么用 全部盒子可以打开的方法除以总的方法数就可以了。 总的方法数好求,就是C(n,k),即在n个盒子中选择k个打开。

对于第一点,打开一连串的盒子,那么最后一个盒子里的钥匙一定是第一个打开盒子的钥匙,比如首先打开2号盒子,那么陆续打开x个盒子以后,

突然发现最后打开的那个盒子里面是2号盒子的钥匙,那么这一连串打开就结束了,也就构成了一个循环。所以很容易联想到组合数学中置换群的循

环节。所以就把所有的循环节都找出来。比如一共有num个循环节,那么能打开全部盒子的条件为给定的钥匙个数k一定要大于等于num,否则最少

有一个循环节里不能打开一个盒子。

对于第二点,求可以打开的方法数采用动态规划递推的方法。首先划分阶段,前面说到一共有num个循环节,那么就把整个问题划分为num个阶

段,每次循环解决一个阶段的问题。接下来是定义状态 ,用dp[ i ] [ j ] ,表示用j把钥匙打开前i个阶段的盒子一共有多少种方法。用到乘法原理,乘

法远离是第一个阶段有a种选择,第二个阶段有b种选择,那么前两个阶段一共有a*b种选择。这里要用到。用递推就要考虑状态的转移:比如当前是

dp [ i ] [ j] , 那么前一个状态为 dp [ i -1] ] [ j - use ]  , 即用j-use把钥匙打开前i-1个阶段的盒子一共有的方法数,也就是说打开第i个阶段的盒子用了

use个钥匙,一共有  C(cnt,use)种方法,cnt为第i个阶段一共有cnt个待打开的盒子。那么根据乘法原理 dp[i][j]=dp[i-1][j-use]*C(cnt,use) ,但是前一

个状态不唯一,也就是use的值可以变化,所以要方法累加 即dp[i][j]+=dp[i-1][j-use]*C(cnt,use).  这里dp[i][j]是未知的,要求它就必须知道dp[i-1][j-

use],也就是用已知的状态去推出未知的状态。

这里用一个例子具体说明一下: 比如一共可以划分为2个阶段,第一个阶段有2个盒子,第二阶段有3个盒子,而给定的钥匙数k为3.

初始dp [ 0 ] [ 0 ] =1;

dp[1][1]+=dp[0][0]*c[2][1] , 第一个阶段里有2个盒子,只用一把钥匙,任选一个盒子开开,一共有c[2][1]种方法

dp[1][2]+=dp[0][0]*c[2][2],  用两把钥匙,只有一种方法

阶段1已求完,用已知的数据去推出未知

dp[2][2]+=dp[1][1]*c[3][1],   乘法原理,第一阶段用了1把钥匙,第二阶段使用一把钥匙,去开第二阶段的3个盒子,任选1个 C[3][1]种方法

dp[2][3]+=dp[1][1]*c[3][2];                                                                  第二阶段使用两把钥匙,去开第二阶段的3个盒子,任选2个C[3][2]种方法

dp[2][3]+=dp[1][2]*c[3][1];                        第一阶段用了2把钥匙,第二阶段使用一把钥匙,去开第二阶段的3个盒子,任选1个C[3][1]种方法


到此本题就分析完了。

值得特别注意的是,最后要用可行方法数除以总的方法数,考虑到精度问题,分子为dp [cnt ][k] 设置为double, 分母组合数也设置成double ,很容易出错。


代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iomanip>
using namespace std;
int n,k;
int match[320];
double c[320][320];
bool vis[320];
double dp[320][320];
vector<int>loop;

void getComb()
{
    for(int i=0;i<=300;i++)
    {
        c[i][0]=c[i][i]=1.0;
        for(int j=1;j<i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
}

int main()
{
    getComb();
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>match[i];
            
        loop.clear();
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)//求循环节
        {
            if(vis[i])
                continue;
            int cnt=0,cur=i;
            while(!vis[cur])
            {
                cnt++;
                vis[cur]=1;
                cur=match[cur];
            }
            loop.push_back(cnt);
        }
        
        int num=loop.size();
        if(k<num)
        {
            printf("%.9lf\n",0.0);
            continue;
        }
        
        memset(dp,0,sizeof(dp));
        dp[0][0]=1.0;
        for(int i=0;i<num;i++)
        {
            for(int j=0;j<k;j++)
            {
                if(dp[i][j]==0)
                    continue;
                for(int use=1;use<=loop[i]&&j+use<=k;use++)
                    dp[i+1][j+use]+=dp[i][j]*c[loop[i]][use];//阶段相乘,前两个阶段的方法数等于第一阶段的方法数*第二阶段的方法数
            }
        }
        printf("%.9lf\n",dp[num][k]/c[n][k]);
    }
}




[ACM] hihoCoder 1075 开锁魔法III (动态规划,组合数学)