Codeforces Round#331(Div.2).D-Wilbur and Trees,例のDFS
7204 ワード
問題の出典:http://www.cnblogs.com/qscqesze/p/4971459.html ゞ膜一发卿学姐Orz...........ゞ
題意はあなたにn本の木をあげて、すべての木の高さはすべて同じhで、およびpで、木を切る時左に倒れる確率、(1-pは右に倒れる確率)、それから2行目はあなたに木の座標を教えていません.木を切る人は毎回0.5の確率で一番左の木を切り、0.5の確率で一番右の木を切り、1本の木を切った後、この木は左か右に倒れ、倒れたときに別の木にぶつかったら、その木も同じ方向に倒れ、ある木を切った後、地面の長さを覆う数学の期待を聞く.
考え方:その时私达はこの问题を见て直接放弃するつもりで、私达はすべて1本のdpだと思って、その上私个人はまた数学の期待に対して少しぼんやりしています(高校の知识はすべて先生に返して、すべての情况の確率*长さの和です).だからこんにゃくの私たちは作れません.その後、問題解を見てみると、本当に難しくない問題(もちろん、自分の頭が悪い)であることがわかりました.この問題はdpを使う必要はありません.与えられた状況ごとに、私たちが考えなければならないのは以下のいくつかの条件です.区間はl-r:lが一番左の木で、rが一番右の木です.1一番左の木を切る(1).左の木を切って左の木を左に倒す場合は、l-1が右に倒れるかどうか、距離はmin(h,v[l]-v[l-1]-f 1(右に倒れるかどうか)*h)であることを考慮する必要があるので、ここのf 1は0であればl-1が左に着き、1であればl-1が右に倒れることを明らかに表す.明らかにまだ終わっていないので、自然に次の区間(l+1,r,0,f 2)をしなければならない.次の区間lに対してl-1に相当するため、左に倒れるとf 1が0になる.同様に、r+1が左または右に倒れるかどうかを判断するためにf 2を設定する.
(2).左の木を切り、左の木を右に倒すのであれば、この木が何本倒せるかを判断する必要があります.右にLを倒せば、この距離は(v[L]-v[l]+h)L+1本目を倒せないに違いないので(存在するなら)考えてみましょう.L=rであれば距離が変わります.r+1が左に倒れるかどうかも考えなければならないので、距離は:(v[r]-v[l]+min(h,v[r+1]-v[r]-f 2*h))であるべきです.この場所は一度書き逃します:(v[r]-v[l]+h f 2*h)が、実はhはv[r+1]-v[r]より大きい可能性が高いので、xjbは書けません!
2.一番右の木を切るのも同じで、右に倒れるのと左に倒れるのと同じである.右に倒れるのは自然に簡単である.すなわちmin(h,v[r+1]-v[r]-f 2*h)+dfs(l,r-1,f 1,0);左に倒れると、自然にlまで押すことができるかどうかを判断する必要があり、できれば(v[r]-v[l]+min(h,v[l]-v[l-1]-f 1*h))である.;Rを倒せる一番左の木にできない場合はv[r]-v[R]+h+dfs(l,R,f 1,1)とする.ここではminを取らず、R-1には当たらないのでh肯定
題意はあなたにn本の木をあげて、すべての木の高さはすべて同じhで、およびpで、木を切る時左に倒れる確率、(1-pは右に倒れる確率)、それから2行目はあなたに木の座標を教えていません.木を切る人は毎回0.5の確率で一番左の木を切り、0.5の確率で一番右の木を切り、1本の木を切った後、この木は左か右に倒れ、倒れたときに別の木にぶつかったら、その木も同じ方向に倒れ、ある木を切った後、地面の長さを覆う数学の期待を聞く.
考え方:その时私达はこの问题を见て直接放弃するつもりで、私达はすべて1本のdpだと思って、その上私个人はまた数学の期待に対して少しぼんやりしています(高校の知识はすべて先生に返して、すべての情况の確率*长さの和です).だからこんにゃくの私たちは作れません.その後、問題解を見てみると、本当に難しくない問題(もちろん、自分の頭が悪い)であることがわかりました.この問題はdpを使う必要はありません.与えられた状況ごとに、私たちが考えなければならないのは以下のいくつかの条件です.区間はl-r:lが一番左の木で、rが一番右の木です.1一番左の木を切る(1).左の木を切って左の木を左に倒す場合は、l-1が右に倒れるかどうか、距離はmin(h,v[l]-v[l-1]-f 1(右に倒れるかどうか)*h)であることを考慮する必要があるので、ここのf 1は0であればl-1が左に着き、1であればl-1が右に倒れることを明らかに表す.明らかにまだ終わっていないので、自然に次の区間(l+1,r,0,f 2)をしなければならない.次の区間lに対してl-1に相当するため、左に倒れるとf 1が0になる.同様に、r+1が左または右に倒れるかどうかを判断するためにf 2を設定する.
(2).左の木を切り、左の木を右に倒すのであれば、この木が何本倒せるかを判断する必要があります.右にLを倒せば、この距離は(v[L]-v[l]+h)L+1本目を倒せないに違いないので(存在するなら)考えてみましょう.L
2.一番右の木を切るのも同じで、右に倒れるのと左に倒れるのと同じである.右に倒れるのは自然に簡単である.すなわちmin(h,v[r+1]-v[r]-f 2*h)+dfs(l,r-1,f 1,0);左に倒れると、自然にlまで押すことができるかどうかを判断する必要があり、できれば(v[r]-v[l]+min(h,v[l]-v[l-1]-f 1*h))である.;Rを倒せる一番左の木にできない場合はv[r]-v[R]+h+dfs(l,R,f 1,1)とする.ここではminを取らず、R-1には当たらないのでh肯定
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define maxn 2005
const int inf = 1e9;
double dp[maxn][maxn][2][2];
int vis[maxn][maxn][2][2];
int n;
double h,p;
int v[maxn];
int dl[maxn],dr[maxn];
double dfs(int l,int r,int f1,int f2) // l,r->1-n f1:l-1 ，f2:r+1
{
//cout<<l<<" "<<r<<" "<<f1<<" "<<f2<<endl;
if(vis[l][r][f1][f2])
return dp[l][r][f1][f2];
if(l>r)
return 0;
vis[l][r][f1][f2]=1; //
//
double ans = dp[l][r][f1][f2];
ans+=p*0.5* ( min(h*1.00,v[l]-v[l-1]-f1*h) + dfs(l+1,r,0,f2) );
// l ，f1=1 l-1 ，
ans+=(1-p)*0.5*(min(h*1.0,v[r+1]-v[r]-f2*h)+dfs(l,r-1,f1,0));
// r ，f2=1 r+1 ，
int L = dr[l];// l ，
int R = dl[r];// r ，
if(R<=l) // r (l)， l。
ans+=p*0.5*( v[r]-v[l] + min(h,v[l]-v[l-1]-f1*h) );// l-1
else // l， 。
ans+=p*0.5*( v[r]-v[R]+h+dfs(l,R-1,f1,1) ); // r R
if(L>=r) // l r，
ans+=(1-p)*0.5*(v[r]-v[l]+min(h,v[r+1]-v[r]-f2*h));
else
ans+=(1-p)*0.5*(v[L]-v[l]+h+dfs(L+1,r,1,f2));
dp[l][r][f1][f2] = ans;
return ans;
}
int main()
{
scanf("%d%lf",&n,&h);
scanf("%lf",&p);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
sort(v+1,v+1+n);
v[n+1]=inf;
v[0]=-inf;
dr[n]=n;dl[1]=1; //dl i ， dr
for(int i=n-1;i>=1;i--){
if(v[i+1]-v[i]<h)
dr[i]=dr[i+1];
else
dr[i]=i;
}
for(int i=2;i<=n;i++){
if(v[i]-v[i-1]<h)
dl[i]=dl[i-1];
else
dl[i]=i;
}
printf("%.15f
",dfs(1,n,0,0));
}