luogu1850换教室

luogu1850换教室

​​ noip竟然引进了 概率和期望 虽然是简单题 可是对于没做过的蒟蒻我还是很难

注意一些细节 这个课程是我一开始就选好了的 而不是我根据 上一次是否选择成功来做下面的

所以我的dp方程应该定义为f[i][j][k]表示我现在在第i个阶段 我已经做了j个申请 K表示我当前阶段是否已经申请

所以转移方程比较长

而且注意 我的概率 可能是两种相乘 比如 我前一次选成功*我这一次没选成功 一共四种可能 认真讨论即可

#include#include#include#define N 2200#define inf 0x3f3f3f3fusing namespace std;double k[N],f[2][N][2];int c[N],d[N],n,m,v,e;int dis[330][330];int main(){// freopen("1850.in","r",stdin); scanf("%d%d%d%d",&n,&m,&v,&e); for (int i=1;i<=n;++i) scanf("%d",&c[i]); for (int i=1;i<=n;++i) scanf("%d",&d[i]); for (int i=1;i<=n;++i) scanf("%lf",&k[i]); memset(dis,0x3f,sizeof(dis)); memset(f,0x42,sizeof(f));for (int i=1;i<=v;++i) dis[i][i]=0; for (int i=1;i<=e;++i){int x,y,tmp; scanf("%d%d",&x,&y); scanf("%d",&tmp); dis[x][y]=dis[y][x]=min(tmp,dis[x][y]); } for (int kk=1;kk<=v;++kk) for (int i=1;i<=v;++i) for (int j=1;j<=v;++j) dis[i][j]=min(dis[i][j],dis[i][kk]+dis[kk][j]); int pre=0,cur=1;f[0][1][1]=f[0][0][0]=0; for (int i=2;i<=n;++i){ for (int j=0;j<=m&&j<=i;++j){ f[cur][j][0]=min(f[cur][j][0],f[pre][j][0]+dis[c[i-1]][c[i]]); f[cur][j][0]=min(f[cur][j][0],f[pre][j][1]+dis[c[i-1]][c[i]]*(1.0-k[i-1])+dis[d[i-1]][c[i]]*k[i-1]); if(j>=1){ f[cur][j][1]=min(f[cur][j][1],f[pre][j-1][1]+dis[c[i-1]][c[i]]*(1.0-k[i-1])*(1.0-k[i])+ dis[d[i-1]][c[i]]*k[i-1]*(1.0-k[i])+dis[d[i-1]][d[i]]*k[i]*k[i-1]+dis[c[i-1]][d[i]]*k[i]*(1.0-k[i-1])); f[cur][j][1]=min(f[cur][j][1],f[pre][j-1][0]+dis[c[i-1]][d[i]]*k[i]+dis[c[i-1]][c[i]]*(1.0-k[i])); } /*f[cur][j][0]=min(min(f[cur][j][0],f[pre][j][0]+dis[c[i-1]][c[i]]),f[pre][j-1][1]+dis[d[i-1]][c[i]]*(1.0-k[i])*k[i-1]); f[cur][j][0]=min(f[cur][j][0],f[pre][j-1][0]+dis[c[i-1]][c[i]]*(1-k[i])*(1-k[i-1])); f[cur][j][1]=min(min(f[cur][j][1],f[pre][j-1][0]+dis[c[i-1]][d[i]])*(1.0-k[i-1])*k[i],f[pre][j-1][1]+dis[d[i-1]][d[i]]*k[i]*k[i-1]); f[cur][j][1]=min();*/ } for (int j=0;j<=m;++j){ f[pre][j][0]=f[pre][j][1]=inf; }//printf("我是分隔符\n"); cur^=1;pre^=1; }double ans=inf; for (int i=0;i<=m;++i) for (int j=0;j<=1;++j) ans=min(ans,f[pre][i][j]); printf("%.2f",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。