题意：有2n个课程安排在n个时间段上，在第i个时间被安排在ci教室上课，但牛牛可以申请换教室，到di教室上课，但只有pi的可能成功。学校有v个教室，e条道路，每条路双向连通，每条路都会消耗一定的体力wi（保证每个教室可以互相到达），问牛牛应该怎么安排，才能使总花费的体力的期望值最小。
输入格式：
第一行四个整数n,m,v,e。n表示时间短的数量；m表示最多可以申请更换教室的数量；v表示教室的数量；e表示道路的数量。
第二行n个正整数，第i个表示ci；
第三行n个正整数，第i个表示di；
第四行n个实数，第i个表示pi；
接下来e行，每行三个正整数ai,bi,wi,表示，有一条双向道路连通ai与bi，消耗的体力为wi；
保证输入的实数最多包含三位小数。
输出格式：
输出一行，包含一个实数，四舍五入到小数点后两位，表示答案。
输入样例：
3 2 3 32 1 21 2 10.8 0.2 0.5 1 2 51 3 32 3 1
输出样例：
2.80
解析：一道数学期望的入门题，dp的方程不难想，dp[i][j][k] 表示前i个教室，换了j次教室，第i个点有没有换所走的最小期望距离。显然 dp[i][j][0] = max（dp[i-1][j][0] + 所需的代价, dp[i-1][j][1] + 所需的代价），dp[i][j][1] = max(dp[i-1][j-1][0] + 所需的代价, dp[i-1][j-1][1] + 所需的代价)。本题的关键便在“所需的代价”上（状态转移特别毒瘤）。转移如下：
dp[i][j][0] = max(dp[i-1][j][0] + 上一个教室与这一个教室的距离, dp[i-1][j][1] + 上一次换教室与这一次的距离*上次换教室成功的几率 + 上一次没换教室与这一次的距离*上一次换教室不成功的几率)；
dp[i][j][1] = max(dp[i-1][j-1][0] + 上一个教室与这个教室换了教室的距离*这个教室换成功的几率 + 上一个教室与这个教室的距离*这个教室换不成功的几率, dp[i-1][j-1][1] + 上一个教室换了与这个教室换了的距离*上个教室换成功的几率*这个教室换成功的几率 + 上一个教室与这个教室的距离*上个教室换不成功的几率*这个教室换不成功的几率 + 上一个教室换了与这个教室的距离*上个教室换成功的几率*这个教室换不成功的几率 + 上个教室与这个教室换了的距离*上个教室换不成功的几率*这个教室换成功的几率)；
注意：换教室成功的几率为pi, 则不成功的几率则为(1-pi)。
转移特别麻烦，而且也特别长。
代码如下：
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 5 int n,m,v,e,w[301][301],c[2001],d[2001]; 6 double p[2001],dp[2001][2001][2],ans=2e9; 7 8 void floyd(void) { //floyd预处理每个教室之间的距离 9 for (int k=1;k<=v;++k) 10 for (int i=1;i<=v;++i) 11 for (int j=1;j<=v;++j) 12 w[i][j]=min(w[i][j],w[i][k]+w[k][j]); 13 } 14 15 int main() { 16 scanf("%d%d%d%d",&n,&m,&v,&e); 17 for (int i=1;i<=n;++i) scanf("%d",&c[i]); 18 for (int i=1;i<=n;++i) scanf("%d",&d[i]); 19 for (int i=1;i<=n;++i) scanf("%lf",&p[i]); 20 for (int i=1;i<=v;++i) 21 for (int j=1;j<i;++j) w[i][j]=w[j][i]=1e9; 22 for (int i=1;i<=e;++i) { 23 int x,y,v; scanf("%d%d%d",&x,&y,&v); 24 w[x][y]=w[y][x]=min(w[x][y],v); //处理重边 25 } 26 floyd(); 27 for (int i=1;i<=n;++i) 28 for (int j=0;j<=m;++j) dp[i][j][1]=dp[i][j][0]=1e9; 29 dp[1][0][0]=dp[1][1][1]=0; //dp初始化 30 for (int i=2;i<=n;++i) 31 for (int j=0;j<=min(i,m);++j) { //恶心的转移 32 dp[i][j][0]=min(dp[i][j][0],min(dp[i-1][j][0]+w[c[i-1]][c[i]],dp[i-1][j][1]+w[d[i-1]][c[i]]*p[i-1]+w[c[i-1]][c[i]]*(1-p[i-1]))); 33 if (j>0) dp[i][j][1]=min(dp[i][j][1],min(dp[i-1][j-1][0]+w[c[i-1]][d[i]]*p[i]+w[c[i-1]][c[i]]*(1-p[i]),dp[i-1][j-1][1]+w[d[i-1]][d[i]]*p[i-1]*p[i]+w[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])+w[c[i-1]][d[i]]*(1-p[i-1])*p[i]+w[d[i-1]][c[i]]*p[i-1]*(1-p[i]))); 34 } 35 for (int i=0;i<=m;++i) ans=min(ans,min(dp[n][i][1],dp[n][i][0])); //不一定要用完所有换教室的机会，所以取min 36 printf("%.2lf",ans); 37 return 0; 38 }
转载于:https://www.cnblogs.com/Gaxc/p/9507211.html
