题意分析

题意分析

本题要求计算在给定字母表 $\{0, 1, \dots, k\}$（$0 \leq k \leq 9$）上，长度为 $n$ 的所有可能单词中，满足相邻数字差不超过1的**紧凑单词（tight word）**所占的百分比。具体来说：

1. 紧凑单词的定义
   对于一个长度为 $n$ 的单词 $w = d_1d_2\dots d_n$，若任意相邻两位数字满足 $|d_i - d_{i+1}| \leq 1$（$1 \leq i < n$），则该单词是紧凑的。

2. 问题核心

   • 动态规划：统计所有可能的紧凑单词数量。
     • 定义状态 $dp[i][d]$ 表示长度为 $i$ 且以数字 $d$ 结尾的紧凑单词数。
     • 转移方程：$dp[i][d] = dp[i-1][d-1] + dp[i-1][d] + dp[i-1][d+1]$（需处理边界 $d=0$ 和 $d=k$）。
   • 数学计算：
     • 总单词数 $= (k+1)^n$。
     • 百分比 $= \left(\frac{\text{紧凑单词数}}{\text{总单词数}}\right) \times 100$。

3. 关键点

   • 高效统计紧凑单词数（动态规划）。
   • 处理大数运算（$n$ 最大为100，需用 double 避免溢出）。
   • 边界条件（$k=0$ 时所有单词均为 00...0，一定紧凑）。

解题思路

用计数dp思想：$DP[I][J]=(DP[I-1][J-1]+DP[I-1][J]+DP[I-1][J+1])$，最后再除$pow(k+1,n)$容易爆精度，改用概率dp思想$DP[I][J]=(DP[I-1][J-1]+DP[I-1][J]+DP[I-1][J+1])/(k+1)$即可。

C++代码实现

//poj 2537
//sep9
#include<iostream>
using namespace std;
double dp[128][16];
 
int main()
{
	int k,n;
	while(scanf("%d%d",&k,&n)==2){
		for(int i=0;i<=n;++i)
			for(int j=0;j<=k;++j)
				dp[i][j]=0;
		for(int i=0;i<=k;++i)
			dp[1][i]=1.0/(k+1);
		for(int i=2;i<=n;++i){
			for(int j=0;j<=k;++j)
				dp[i][j]=dp[i-1][j]/(k+1);
			for(int j=1;j<=k;++j)
				dp[i][j]+=dp[i-1][j-1]/(k+1);
			for(int j=0;j<k;++j)
				dp[i][j]+=dp[i-1][j+1]/(k+1);
		}
		double sum=0;
		for(int i=0;i<=k;++i)
			sum+=dp[n][i];
		printf("%.5lf\n",sum*100);
	}
	return 0;	
}