首页 > ACM题库 > 九度OJ > 九度-1338-角斗士[状态压缩DP]
2014
02-02

九度-1338-角斗士[状态压缩DP]

题目来自九度OJ之我与名企有个约会趣味编程系列赛(1)

题目描述:
角斗士是古罗马奴隶社会的一种特殊身份的奴隶,他们的职责是在角斗场上进行殊死搏斗,为了人们提供野蛮的娱乐。他们的结局或是战死,或者由于表现突出赢得胜利而获得释放。
现在在角斗场里有N个待战的角斗士(1 <=N<=18),每天都将举行一场比赛,为了保持比赛的刺激性,每场比赛前才会在所有当前活着的角斗士之中随机选择两名进行上场拼杀。每场比赛的结束条件即为其中一名被杀死。当进行了N场比赛之后,最后存活的角斗士将被释放。而你将被赋予一个任务,计算出每名角斗士最终存活的概率。我们将提供角斗士之间对战获胜的概率。
输入:
测试数据包括多个,每个测试数据包含两部分
首先第一行将输入一个整数N,其中1 <= N <= 18,代表角斗士的个数。
接下来将是一个N * N大小的概率矩阵P,代表角斗士之间战斗的获胜概率,例如P[i][j]就代表角斗士i战胜j的概率;同样P[j][i]则代表角斗士j战胜i的概率。我们保证P[i][j] + P[j][i] = 1。同时我们规定当i等于j时,P[i][j] 为 0。
输出:
对于每个测试案例,输出一行,包含N个小数,中间用空格隔开,分别代表第0、1、…、N个角斗士存活下来的概率,每个小数精确到小数点后3位。
样例输入:
2
0 0.5
0.5 0
3
0 1 1
0 0 0.5
0 0.5 0
样例输出:
0.500 0.500
1.000 0.000 0.000

思路:
状态压缩DP。
令数组dp[x]表示x在二进制上为1那些人活着的概率,比如现在只有3个人,
那么dp[5]表示第一个人和第三个人活着的概率。
由于比赛是随即选择两个人,那么每场比赛的概率为1 / C(活着的人的个数,2)。
最终的概率应该是叠加上去。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;

double p[20][20];
double dp[1<<18];
int main(){
        int n;
        while(scanf("%d",&n)==1){
                for(int i=0;i<n;i++)
                        for(int j=0;j<n;j++)
                                scanf("%lf",&p[i][j]);
                int dest=(1<<n)-1;
                for(int i=0;i<=dest;i++)
                        dp[i]=0;
                dp[0]=1;
                for(int i=0;i<dest;i++){
                        int cnt=0;
                        for(int j=0;j<n;j++)
                                if(((1<<j)&i)==0)
                                        cnt++;
                        int total=cnt*(cnt-1)/2;
                        if(!total) continue;
                        for(int j=0;j<n;j++){
                                if((1<<j)&i) continue;
                                for(int k=j+1;k<n;k++){
                                        if((1<<k)&i) continue;
                                        dp[i|(1<<k)]+=dp[i]*p[j][k]/total;
                                        dp[i|(1<<j)]+=dp[i]*p[k][j]/total;
                                }
                        }
                }
                for(int i=0;i<n;i++){
                        if(i==n-1)
                                printf("%.3lf\n",dp[dest^(1<<i)]);
                        else
                                printf("%.3lf ",dp[dest^(1<<i)]);
                }
        }
}

 


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  4. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  5. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮