BNU 34978 漢諾塔 求期望步數

BNU 34978 漢諾塔 求期望步數

題目鏈接：點擊打開鏈接

我們用dp[i]表示 隨機i個盤子時，恢復原位需要的步數的期望

f[i]表示i個盤子下普通的漢諾塔玩法的步數

既然是隨機，那麼我們就認為是在上一次隨機的情況下，

把第n個放到任意一根柱子的底部

那麼若隨機放到了第3個柱子，則步數就是dp[n-1]

若放到了第1根柱子，則先把前面的n-1個盤子移動到第2根柱子上，花費是dp[n-1]

然後再把n盤子移動到第三根柱子，再把其他盤子移動到第三根柱子， 花費是 1+f[n-1]

就是這樣_(:зゝ∠)_

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 100
#define ll long long
ll n;
double f[N];
double dp[N];
int main() {
    f[1] = 1.0;
    for(int i = 2; i < N; i++) f[i] = f[i-1]*2.0+1.0;
    dp[1] = 0.666666666666666;
    for(int i = 2; i < N; i++)
        dp[i] = dp[i-1]/3.0 + 2.0 * (dp[i-1] + f[i-1] +1.0) / 3.0;
    int T, j;scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&j);
        printf("%.2f\n", dp[j]);
    }
    return 0;
}