题目链接：点击打开链接
题意：
要在一条直线上摆多米诺骨牌。
输入n, l, r
要摆n张排，每次摆下去向左倒的概率是l, 向右倒的概率是r
可以采取最优策略，即可以中间放一段，然后左右两边放一段等，摆放顺序任意。
问：在最佳策略下要摆成n张牌的期望次数。
思路：
点击打开链接
#include #include #include #include #include #include #include template inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; typedef long long ll; #define N 2002 const ll mod = 1e9+7; int n; double l, r; double dp[N]; double solve(){ dp[0] = 0; dp[1] = 1.0/(1.0-l-r); for(int i = 2; i <= n; i++) { dp[i] = 1e18; for(int j = 0; j < i; j++) { int L = j, R = i-j-1; double x = (1+ dp[L] + dp[R] -dp[L]*r -dp[R]*l) / (1-l-r); dp[i] = min(dp[i], x); } } return dp[n]; } int main() { while(cin>>n>>l>>r, n){ printf("%.2f\n", solve()); } return 0; }