1990623 2006-08-01 16:53:10 Accepted 2271 C++ 00:00.77 8324K St.Crux 过的好不容易...... 要求A与B在不同时间点上相遇的概率和。很明显的dp，用不同的时间来区分状态。郁闷的是一开始居然看不懂样例...... p[t][i][k] = OMG([t - 1][ii][kk] / 概率) 这里iikk是与i,k相邻的点。 用了两个优化。一是算概率的时候可以用以下init的方法。二是染色！如5,9,13,17这样的是无解的:( #include <cstdio>#include <string> double p[101][100][100];int pos[100][100], n; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; void init(){ for(int i = 0; i < n; i ++) {  for(int k = 0; k < n; k ++)  {   pos[i][k] = 4;   if(i == 0 || i == n - 1)    pos[i][k] --;   if(k == 0 || k == n - 1)    pos[i][k] --;  } }} int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d", &n) != EOF) {  memset(p, 0, sizeof(p));  init();  int t, i, k, u;  double p_p = 1.0000, s_p = 0.0000;  if((n - 3) % 4 == 0)  {  p[0][n / 2][n / 2] = p_p;   for(t = 1; t <= n; t ++)  {   for(i = 0; i < n; i ++)   {    for(k = 0; k < n; k ++)    {     p_p = 0.0000;     for(u = 0; u < 4; u ++)     {      int ii = i + dir[u][0];      int kk = k + dir[u][1];      if(kk >= 0 && kk < n && ii >= 0 && ii < n)      {       p_p += p[t - 1][ii][kk] / pos[ii][kk];      }     }     p[t][i][k] = p_p;    }   }   s_p += p[t][n / 2][t - 1];   p[t][n / 2][t - 1] = 0;  }  }  //pt();  printf("%0.4f\n", s_p); } return 0;}

评论