POJ 2537 Tight words

問題

[0...k](0<= k <= 9)の文字を使って長さnの文字列を作る。隣り合った文字の差がすべて1以下であるとき、その文字列をtightという。全文字列中のうちのtightな文字列の割合を百分率で求めよ。

やりかた

DP。
dp[i][j]:=（長さiの文字列で最後の文字がjであるようなtightな文字列が発生する割合（百分率））とする。dpでtightな文字列の総パターン数を求めて(k+1)^nで割ることもできるが、C++では多倍長整数を使わないとできないのでここでは割合のまま計算した。

以下ソース。

double dp[101][10];
int main(int argc, char **argv){
  int k, n;
  while(scanf("%d %d", &k, &n) != EOF){
    FILL(dp, 0);
    for(int i = 0; i < 10; i++) dp[1][i] = 100;
    for(int i = 1; i < n; i++){
      for(int j = 0; j <= k; j++){
	if(j - 1 >= 0) dp[i + 1][j] += dp[i][j - 1] / (k + 1);
	if(j + 1 <= k) dp[i + 1][j] += dp[i][j + 1] / (k + 1);
	dp[i + 1][j] += dp[i][j] / (k + 1);
      }
    }
    double ans = 0;
    for(int i = 0; i <= k; i++) ans += dp[n][i];
    printf("%.5f\n", ans / (k + 1));
  }
  return 0;
}