首页 > 代码库 > UESTC 电子科大专题训练 DP-E
UESTC 电子科大专题训练 DP-E
UESTC 1652
题意:中文题
思路:遍历每一公里,然后计算每个车道对后一公里做出的贡献,最边上的车道特判,遍历完所有车道后判断如果车道上有障碍,那么这公里的的这个车道的概率为0,数据比较水,如果数据大可以用矩阵快速幂对每2个障碍之间用矩阵快速幂优化,这里就不写了
AC代码:
#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=1e5+100; const ll mod=1e9+7; double dp[2][30005],ans; int ma,n,m,k,a,b,p; vector<int> pp[1005]; int main(){ //ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>m>>k>>n>>p; for(int i=1; i<=k; ++i){ cin>>a>>b; pp[b].pb(a); ma=max(ma,b); } dp[0][p]=1; double *now=dp[0], *nex=dp[1]; for(int i=1; i<=ma; ++i){ for(int j=1; j<=m; ++j){ if(j==1){ nex[j]+=now[j]/2; nex[j+1]+=now[j]/2; } else if(j==m){ nex[j]+=now[j]/2; nex[j-1]+=now[j]/2; } else{ nex[j]+=now[j]/3; nex[j+1]+=now[j]/3; nex[j-1]+=now[j]/3; } } for(auto j : pp[i]){ nex[j]=0; } swap(now,nex); memset(nex,0,sizeof(dp[0])); } for(int i=1; i<=m; ++i){ ans+=now[i]; } printf("%.6f\n",ans); return 0; }
UESTC 电子科大专题训练 DP-E
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。