题解：UVA10081 Tight Words

题目翻译：

点击查看。

思路：

使用动态规划，计算在给定的字母表上，长度为 $n$ 的所有可能单词中，“紧致”单词的数量。

然后，通过这个数量除以所有可能的单词数量来计算出“紧致”单词的百分百。

对于 $dp_{i,j}$，其中 $i$ 表示长度为 $i$，$j$ 表示以 $j$ 结尾，当长度为 $1$ 时，每个数字 $j$ 都是一个“紧致”单词，因此我们可以初始化所有 $dp_{1,j}$ 为 $1$，其中 $0 \le j \le k$。

对于 $i$ 不等于 $1$ 时的 $dp_{i,j}$ 等于什么呢？这需要分类讨论。

对于长度为 $i$ 且以数字 $j$ 结尾的单词，它可以从以下几种情况转移而来：

1. 长度为 $i-1$ 且以数字 $j$ 结尾的单词。
2. 长度为 $i-1$ 且以数字 $j-1$ 结尾的单词，注意 $j$ 需要大于 $0$。
3. 长度为 $i-1$ 且以数字 $j+1$ 结尾的单词，注意 $j$ 需要小于 $k$。

因此，动态转移方程在 c++ 中可以表示为：

dp[i][j]+=dp[i-1][j];
if(j!=0)dp[i][j]+=dp[i-1][j-1];
if(j!=k)dp[i][j]+=dp[i-1][j+1];

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k;
double dp[110][15]; 
void solve(){
	memset(dp,0,sizeof(dp));
	for(int i=0;i<=k;i++)dp[1][i]=1;
	for(int i=2;i<=n;i++){
		for(int j=0;j<=k;j++){
			dp[i][j]+=dp[i-1][j];
			if(j!=0)dp[i][j]+=dp[i-1][j-1];
			if(j!=k)dp[i][j]+=dp[i-1][j+1];
		}
	}
	double sum=0;
	double kn=pow(k+1,n);
	for(int i=0;i<=k;i++)sum+=dp[n][i];
//	cout<<sum<<" "<<kn<<"\n";
	double ans=sum*100;
	ans/=kn;
	printf("%.5lf\n",ans);
//	cout<<fixed<<setprecision(5)<<(sum*100.0)/kn<<"\n";
	return;
} 
int main(){
	while(cin>>k>>n)solve();
	return 0;
}