題意：

你試圖把一些多米諾骨牌排成直線，然后推倒它們。但是如果你在放骨牌的時候不小心把剛放的骨牌碰倒了，它就會把相臨的一串骨牌全都碰倒，

而你的工作也被部分的破壞了。

比如你已經把骨牌擺成了DD__DxDDD_D的形狀，而想要在x這個位置再放一塊骨牌。它可能會把左邊的一塊骨牌或右邊的三塊骨牌碰倒，而你將不得不重新擺放這些骨牌。

這種失誤是無法避免的，但是你可以應用一種特殊的放骨牌方法來使骨牌更多的向一個方向倒下。

給出你要擺放的骨牌數目，以及放骨牌時它向左和向右倒的概率，計算你為完成任務擺放的骨牌數目的平均數。假設你使用了最佳的擺放策略。

輸入將包含至多100個測試點，每個測試點占一行，包含需要擺放的骨牌數目n?(1≤n≤1000)，以及兩個非負實數Pl,?Pr，表示骨牌向左和向右倒的概率。保證1＜Pl+Pr≤0.5。

解析：

　　假設我們正在放第i個 ?i的左右兩邊都已經放好了 那么 有三種情況 ?左倒 ? 右倒 ?不倒?

　　設放左邊的期望次數為El ?放右邊的期望次數為Er?

　　那么E_i?就等于相應 情況乘概率然后相加

　　如果不倒 Ei = El + Er + 1；

　　如果 左倒 那么我們就要重新放一遍左邊 那么次數增加El + 1 次？ ?仔細想一下 當然不是。。因為如果這次再放的時候又倒了那 ?所以是Ei - Er

　　同理 如果右倒 則是 Ei - El

　　所以 Ei = El + Er + 1 + （Ei - Er）* pl + （Ei - El）* pr；

　　移項得?

Ei = min(Ei, (1 - p1) / (1 - p1 - p2) * El + (1 - p2) / (1 - p1 - p2) * Er + 1 / (1 - p1 - p2)；

?

?

#include <iostream>
#include <cstdio> #include <sstream> #include <cstring> #include <map> #include <cctype> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #include <bitset> #define rap(i, a, n) for(int i=a; i<=n; i++) #define rep(i, a, n) for(int i=a; i<n; i++) #define lap(i, a, n) for(int i=n; i>=a; i--) #define lep(i, a, n) for(int i=n; i>a; i--) #define rd(a) scanf("%d", &a) #define rlld(a) scanf("%lld", &a) #define rc(a) scanf("%c", &a) #define rs(a) scanf("%s", a) #define pd(a) printf("%d\n", a); #define plld(a) printf("%lld\n", a); #define pc(a) printf("%c\n", a); #define ps(a) printf("%s\n", a); #define MOD 2018 #define LL long long #define ULL unsigned long long #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int maxn = 1700, INF = 0x7fffffff, LL_INF = 0x7fffffffffffffff; int n, m, tot; double dp[maxn];int main() {int n;double p1, p2;while(cin >> n >> p1 >> p2){for(int i=1; i<=n; i++){dp[i] = INF;for(int j=0; j<i; j++)dp[i] = min(dp[i], (1 - p1) / (double) (1 - p1 - p2) * dp[j] + (1 - p2) / (double) (1 - p1 - p2) * dp[i - j - 1]);dp[i] += 1 / (double)(1 - p1 - p2);}printf("%.2f\n", dp[n]);}return 0; }

?

轉載于:https://www.cnblogs.com/WTSRUVF/p/9733632.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Dumb Bones UVA - 10529（概率dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。