## 题目描述

You are trying to set up a straight line of dominos, standing on end, to be pushed over later for your entertainment. (Sure, it seems pointless to set something up only to knock it down again, but you have some strange hobbies) The tricky thing about setting dominos, however, is that if you make a mistake and knock one over as you place it, it will knock down any adjacent line of consecutive dominos on one side of it, partially ruining your work.

For instance, if you've already placed dominos in the pattern DD__DxDDD_D, and you try placing a domino at position x, there is a chance it will fall and knock over the domino to the left or the three dominos to its right, forcing you to place them again.

This human error is somewhat unavoidable, but you can make the odds somewhat more favourable by using a domino-placing technique that leads to dominos falling in one direction more often than in the other.

Given the number of dominos you are trying to set up, and the probability that you'll knock over any individual domino either to the left or to the right while placing it, determine the average number of dominos you'll need to place before you finish. Assume that you're using an optimal placement strategy.

## 输入

The last test case is followed by a line containing a single 0.

## 输出

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 const int maxn = 1100; 5 int n; 6 double l,r; 7 double dp[maxn]; 8 double calc (int n,int x) 9 { 10 return (1.0+l*dp[x-1]+r*dp[n-x])/(1-l-r)+dp[x-1]+dp[n-x]; 11 } 12 int main() 13 { 14 //freopen("de.txt","r",stdin); 15 while (~scanf("%d",&n)){ 16 if (n==0) break; 17 scanf("%lf%lf",&l,&r); 18 dp[0]=0; 19 dp[1]=1.0/(1-r-l); 20 for (int i=2;i<=n;++i){ 21 dp[i]=calc(i,i); 22 for (int j=1;j<=i;++j) 23 dp[i]=min(dp[i],calc(i,j)); 24 } 25 printf("%.2f\n",dp[n]); 26 } 27 return 0; 28 }

优化成O(n)

1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 double f[100005]; 5 double pl,pr,ans; 6 int n; 7 inline double cal(int n,int i){ 8 return (pl*f[i-1]+pr*f[n-i]+1)/(1.0-pl-pr)+f[i-1]+f[n-i];//计算期望 9 } 10 int main(){ 11 cin>>n; 12 int i,j,x=1; 13 cin>>pl>>pr; 14 f[0]=0;f[1]=1.0/(1.0-pl-pr);//初始化，0张牌期望为0，一张牌期望为既不左倒也不右倒的概率 15 for(i=2;i<=n;i++){ 16 f[i]=cal(i,x); 17 while(x<i&&cal(i,x+1)<f[i]){f[i]=cal(i,x+1);x++;}//更优的决策点一定在上一次决策点之后 18 } 19 printf("%.2lf",f[n]);//保留两位 20 return 0; 21 }