首页 > 代码库 > 【概率dp】【滚动数组】CDOJ1652 都市大飙车
【概率dp】【滚动数组】CDOJ1652 都市大飙车
转移方程很显然。
因为是多段图模型,所以可以滚动数组优化一维空间。
#include<cstdio> #include<cstring> using namespace std; int m,K,n,p; bool zaw[1010][30010]; double f[2][30010]; int main(){ int x,y; bool flag=1; scanf("%d%d%d%d",&m,&K,&n,&p); for(int i=1;i<=K;++i){ scanf("%d%d",&x,&y); if(y<=n){ zaw[y][x]=1; flag=0; } } if(m==1){ if(!flag){ puts("0.000000"); } else{ puts("1.000000"); } return 0; } bool cur=0; f[cur][p]=1; for(int i=1;i<=n;++i){ cur^=1; memset(f[cur],0,sizeof(f[cur])); for(int k=1;k<=2;++k){ if(!zaw[i-1][1]){ f[cur][k]+=f[cur^1][1]/2.0; } } for(int k=m-1;k<=m;++k){ if(!zaw[i-1][m]){ f[cur][k]+=f[cur^1][m]/2.0; } } for(int j=2;j<m;++j){ for(int k=j-1;k<=j+1;++k){ if(!zaw[i-1][j]){ f[cur][k]+=f[cur^1][j]/3.0; } } } } double ans=0; for(int i=1;i<=m;++i){ if(!zaw[n][i]){ ans+=f[cur][i]; } } printf("%.6lf\n",ans); return 0; }
【概率dp】【滚动数组】CDOJ1652 都市大飙车
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。