题意:有一些高度为h的树在数轴上。每次选择剩下的树中最左边或是最右边的树推倒(各50%概率),往左倒有p的概率,往右倒1-p。

一棵树倒了,如果挨到的另一棵树与该数的距离严格小于h,那么它也会往同方向倒。

问所有树都被推倒后的期望覆盖长度?

n<=2000.

标程:

 #include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int inf=1e8+;
const int N=;
int pos[N],h,n,L[N],R[N];
double p,dp[N][N][][];
int check(int op,int x,int dir)
{
if (op==)
{
if (!dir) return min(pos[x]-pos[x-],h);
else return min(h,max(pos[x]-pos[x-]-h,));
}else {
if (!dir) return min(h,max(pos[x+]-pos[x]-h,));
else return min(pos[x+]-pos[x],h);
}
}
double dfs(int x,int y,int l,int r)
{
if (x>y) return ;
if (dp[x][y][l][r]) return dp[x][y][l][r];
double &ans=dp[x][y][l][r];
//choose left
ans+=0.5*p*(dfs(x+,y,,r)+check(,x,l));//fall left
if (R[x]+<=y) ans+=0.5*(-p)*(dfs(R[x]+,y,,r)+pos[R[x]]-pos[x]+h);//fall right
else ans+=0.5*(-p)*(pos[y]-pos[x]+check(,y,r));
//choose right
ans+=0.5*(-p)*(dfs(x,y-,l,)+check(,y,r));//fall right
if (x<=L[y]-) ans+=0.5*p*(dfs(x,L[y]-,l,)+pos[y]-pos[L[y]]+h);//fall left
else ans+=0.5*p*(pos[y]-pos[x]+check(,x,l));
return ans;
}
int main()
{
scanf("%d%d%lf",&n,&h,&p);
for (int i=;i<=n;i++) scanf("%d",&pos[i]);
sort(pos+,pos+n+);pos[]=pos[]-h;pos[n+]=pos[n]+h;
L[]=;R[n]=n;
for (int i=;i<=n;i++)
if (i==||pos[i]-pos[i-]<h) L[i]=L[i-];else L[i]=i;
for (int i=n-;i>=;i--)
if (i==n||pos[i+]-pos[i]<h) R[i]=R[i+];else R[i]=i;
printf("%.10lf\n",dfs(,n,,));
return ;
}

易错点:1.注意长度的判断。分类讨论。

2.需要设置极值端点,和1树、n树的距离要>=h。

题解:区间dp

剩下的一段树一定是连续的,区间dp即可。分四种情况讨论推导情况。

预处理一棵树往左/往右倒影响多少棵树。注意计算距离。

最新文章

  1. Frida HOOK微信实现骰子作弊
  2. 学习笔记:MySQL字符串类型
  3. java学习笔记--java中的基本数组[5]
  4. ArcGIS提取影像边界
  5. 三门概率问题之C#版
  6. FieldInfo.IsSpecialName Property【转】
  7. html5 canvas 实现一个简单的叮当猫头部
  8. Broadcast Receiver注意事项
  9. SAP 月结F.19与GR/IR
  10. 用Django做一个团队介绍
  11. python浅拷贝和深拷贝
  12. vs2015编译caffe
  13. SummerNote 富文本编辑器 - Rails 集成
  14. python 标准库 glob ,python glob 学习
  15. @CrossOrigin注解与跨域访问
  16. 20170907wdVBA_GetCellsContentToExcel
  17. python介绍与入门
  18. cool
  19. tkinter Canvas画图片大坑总结
  20. 记开发个人图书收藏清单小程序开发(五)Web开发

热门文章

  1. spring其他配置 (3)
  2. JAVA泛型知识(一)
  3. Codeforces 479【B】div3
  4. 判断APP是否已安装
  5. iOS开发系列-HTTPS
  6. 服务启动脚本start_boot.sh
  7. SPR, subpixel rendering
  8. 2016.8.15上午纪中初中部NOIP普及组比赛
  9. C++ 贪吃蛇一维
  10. Windows ipconfig