AOJ1277 Minimal Backgammon

Minimal Backgammon

Here is a very simple variation of the game backgammon, named "Minimal Backgammon". The game is played by only one player, using only one of the dice and only one checker (the token used by the player). The game board is a line of ( N + 1) squares labeled as 0 (the start) to N (the goal).

動的計画法．

とする．ターン目にマスにいる時にサイコロを振るのは

と書ける．一回休みの時は，戻るマスは に遷移する．マスを追い越した時に戻ってくる処理でバグバグした．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

double dp[105][105];

int main() {
  int n, t, l, b;
  while(cin >> n >> t >> l >> b) {
      if(n == 0 && t == 0 && l == 0 && b == 0) break;

      memset(dp, 0, sizeof(dp));

      bool lose[105], back[1005];
      memset(lose, 0, sizeof(lose));
      memset(back, 0, sizeof(back));

      rep(i, l) {
          int x;
          cin >> x;
          lose[x] = true;
      }

      rep(i, b) {
          int x;
          cin >> x;
          back[x] = true;
      }

      memset(dp, 0, sizeof(dp));

      dp[0][0] = 1.0;
      rep(i, t) {
          rep(j, n) {
              if(dp[i][j] == 0.0) continue;
              REP(k, 1, 7) {
                  int p = j + k;
                  if(p > n) p = n - (p - n);

                  if(lose[p]) {
                      dp[i+2][p] += dp[i][j] * (1.0 / 6.0);
                  } else if(back[p]) {
                      dp[i+1][0] += dp[i][j] * (1.0 / 6.0);
                  } else {
                      dp[i+1][p] += dp[i][j] * (1.0 / 6.0);
                  }
              }
          }
      }

      double ans = 0;
      rep(i, t + 1) {
          ans += dp[i][n];
      }

      cout << fixed;
      cout.precision(20);
      cout << ans << endl;
  }

  return 0;
}
Mar 18th, 2016
250, aoj-icpc, 動的計画法, 確率