过的好不容易......

要求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;
}

评论