[ACM]CCF CSP [201612-5]E题 卡牌游戏【75分的程序】

思路：马尔可夫过程，转为求解方程组：每一种状态有一个概率，把概率转移方程列出来，用高斯消元法求解。

由于一共有2^n-2个方程，n最大为15，高斯消元法解方程是三次方的，无法通过极限数据。方程组是稀疏的，不知道要怎么优化。

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define N 15
#define pw(x) (1< qry;
int read(){scanf("%d%d",&n,&m);for (int i=1;i0) //S状态是否包含卡牌c
#define FORSTATE(S,c) for (int c=1;c<=n;c++)if (CONTAIN(S,c))  //枚举S中的卡牌
double p1[N];
double p2[N];
double sum[N];
void calcP1P2(int S,double* p1){ //计算在状态S时，出每张牌的概率int S2=OPPSTATE(S);for (int i=1;i<=n;i++) p1[i]=sum[i]=0.0;double ssum=0;FORSTATE(S,c1){FORSTATE(S2,c2){sum[c1]+=p[c1][c2];}ssum+=sum[c1];}FORSTATE(S,c1) p1[c1]=sum[c1]/ssum;
}
void calcA(){                      //计算两两状态转移概率memset(a,0,sizeof(a));for (int S=1;S<(1<%d %.2lf\n",S,S^pw(i-1),a[S][i]);}}}
double mat[5000][5000];
void gauss(){//2^n-2个方程memset(mat,0,sizeof(mat));int sz=(1< fabs(mat[r][i])) r=j;}if (r!=i) for (int j=1;j<=sz+1;j++) swap(mat[i][j],mat[r][j]);for (int j=1;j<=sz;j++)if (j!=i){double f=mat[j][i]/mat[i][i];for (int k=i;k<=sz+1;k++) mat[j][k]-=f*mat[i][k];}}//printf("\nafter gausss\n");for (int i=1;i<=sz;i++,putchar('\n'))//for (int j=1;j<=sz+1;j++)printf("%.2lf ",mat[i][j]);for (int i=1;i<=sz;i++){mat[i][sz+1]/=mat[i][i];// printf("STATE[%d] %.2lf\n",i,mat[i][sz+1]);}mat[0][sz+1]=0.0;mat[sz+1][sz+1]=1.0;
}
int main(){read();calcA();gauss();for (int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！