P1850 [NOIP2016 提高组] 换教室

小h很久以前就想做这题了，但是一看到动态规划、期望就怕，更何况这一题两个都包含了呢？不过他没做过的noip真题已经不多了，也是时候练习动态规划了（再不练就来不及了）。先看看细节：1、存在重边和自环，教室不超过300个，所以用临接表存图，重边取最小的，自己到自己取0。2、浮点数的初始化不能用memset，要用循环，我的是1e20，因为double是科学计数法，所以可以大一点。

首先用弗洛伊德找到任意两个教室之间的最小体力。

设计动态规划的状态dp（n，m，01），这个应该不难想到。dp（i，j，0）代表到第i节课为止，申请了j节课，第i节课是（1）否（0）申请了。然后赋初值，先全部为无穷，并且dp（1，0，0）和dp（1，1，1）为0，因为不管怎样，第一节课换不换，当时都还没有走路，不消耗体力。

接下来讲讲什么是期望。就是不同数值乘产生该数值的概率的和。比如小h有0.5的概率拥有2块，0.5的概率拥有4块，则他的期望存款为0.5*2+0.5*4=3(块)。

回到题目，我们知道不同最短路之间是独立的，也就是说从上课地点x到y，与上课地点a到b的期望体力值无关，所以可以预处理出每一节课和上一节课路径消耗体力值的期望NN(i),NY(i),YY(i),YN(i)，分别代表第i-1节课和第i节课都不申请换教室、第i-1节课不申请而第i节课申请、第i-1节课和第i节课都申请、第i-1节课申请而第i节课不申请。以YY为例，都申请了，但是有4种可能：成功成功、成功失败、失败成功、失败失败。根据乘法原理，成功成功的概率为k（i）*k(i-1)，体力为dis(d(i-1),d(i))。成功失败的概率为k(i-1)*(1-k(i))，体力为dis(d(i-1),c(i))，以此类推，把4种情况的概率和体力乘积相加，和为YY（i）

NN、NY、YN同理。

状态转移：自己看代码吧。应该已经很清楚了。没时间写qwq

小h我尽量写清楚，看不懂没事，把代码复制到文本编辑器自己看，多动手，耐心调试，相信你会有收获。

正解#include<bits/stdc++.h>

defineLL double

defineINF 1e+20

defineN 2003

using namespace std;

int n,m,v,e,c[N],d[N];

LL a[N],dis[N][N],dp[N][N][2],NN[N],YN[N],NY[N],YY[N],ans;

int main(){

//freopen("1.in","r",stdin);

scanf("%d%d%d%d",&n,&m,&v,&e);

int i,j,k,c1,c2,d1,d2;

for(i=1;i<=v;i++) for(j=1;j<=v;j++) dis[i][j]=i==j ? 0 : INF;

for(i=1;i<=n;i++)

for(j=0;j<=m;j++){

dp[i][j][0]=INF; dp[i][j][1]=INF;

}

dp[1][0][0]=0; dp[1][1][1]=0;

for(i=1;i<=n;i++) scanf("%d",c+i);

for(i=1;i<=n;i++) scanf("%d",d+i);

for(i=1;i<=n;i++) scanf("%lf",a+i);

for(i=0;i<e;i++){

LL x;

scanf("%d%d%lf",&j,&k,&x);

x=min(dis[j][k],x); dis[j][k]=x; dis[k][j]=x;

}

for(k=1;k<=v;k++)

for(i=1;i<=v;i++)

for(j=1;j<=v;j++)

dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

for(i=2;i<=n;i++){

c1=c[i-1]; c2=c[i]; d1=d[i-1]; d2=d[i];

LL ac1(1-a[i-1]),ac2(1-a[i]),ad1(a[i-1]),ad2(a[i]);

NN[i]=dis[c1][c2];

NY[i]=dis[c1][d2]*ad2+dis[c1][c2]*ac2;

YN[i]=dis[d1][c2]*ad1+dis[c1][c2]*ac1;

YY[i]=dis[d1][d2]*ad1*ad2+dis[d1][c2]*ad1*ac2+

dis[c1][d2]*ac1*ad2+dis[c1][c2]*ac1*ac2;

dp[i][0][0]=dp[i-1][0][0]+NN[i];

}

ans=dp[n][0][0];

for(i=2;i<=n;i++)

for(j=1;j<=m;j++){

dp[i][j][0]=min(dp[i-1][j][0]+NN[i],dp[i-1][j][1]+YN[i]);

dp[i][j][1]=min(dp[i-1][j-1][0]+NY[i],dp[i-1][j-1][1]+YY[i]);

if(i==n) ans=min(ans,min(dp[i][j][0],dp[i][j][1]));

}

printf("%.2lf",ans);

return 0;

}

小h

小h另外，代码都是我自己耐心编写、调试的, 是C++语言，不是无意义的灌水符号，不要举报，何况没有规定只能用中文吧？我只是一个想力所能及帮助广大OI爱好者进步，同时加强自己对算法理解的蒟蒻。