解题思路
很明显的是个期望 $dp$。
先前想到 $dp[i][j]$ 表示第决策到第 $i$ 个时间段，已经进行了 $j$ 次申请，然后就没有然后了，因为这根本就没法转移啊，你又不知道前 $i-1$ 个时间段里哪一个时间段是申请换教室了的。所以此路不通，另寻他路---题解。天哪没有题解还咋做题啊
不妨再加入一维 $[0/1]$ 表示第 $j$ 个时间段有没有进行申请操作
那么就分为一下两种情况
第 $i$ 个时间段申请了第 $i$ 个时间段没有申请
那么这两种状态分别是 $dp[i][j][1]$ 和 $dp[i][j][0]$，我们然后这个期望的话是距离乘以我走这段路的概率
算第一种情况 ( $dp[i][j][1]$ ) 包含的概率又分为下面的四种情况
我从 $c[i-1]\rightarrow c[i]$，这时候概率是 $(1-k[i-1])\times (1-k[i])$我从 $c[i-1]\rightarrow d[i]$，这时候概率是 $(1-k[i-1])\times k[i]$我从 $d[i-1]\rightarrow c[i]$，这时候概率是 $k[i-1] \times (1-k[i])$我从 $d[i-1]\rightarrow d[i]$，这时候概率是 $k[i-1]\times k[i]$
再算第二种情况 ( $dp[i][j][0]$ ) 包含的概率又分为两种情况
我从 $c[i-1]\rightarrow c[i]$，这时候概率是 $(1-k[i-1])$我从 $d[i-1]\rightarrow c[i]$，这时候概率是 $k[i-1]$
上述的大类情况仅为 $i-1$ 这个时间段进行了申请 ( $dp[i-1][j-1][1]\ or\ dp[i-1][j][1]$ )。
下面说另一种情况 ( $dp[i-1][j-1][0]\ or\ dp[i-1][j][0]$ )
第一种情况 ( $dp[i][j][1]$ )
我从 $c[i-1]\rightarrow c[i]$，概率是 $1-k[i]$我从 $c[i-1]\rightarrow d[i]$，概率是 $k[i]$
第二种情况 ( $dp[i][j][0]$ )
我从 $c[i-1]\rightarrow c[i]$，概率是 $1$
这就是所有的情况。
至于两个点之间的最短距离因为点的数量不超过 $300$，所以可以用 $\text{Floyd}$ 来处理
状态转移方程将上面的东西稍微整理一下就出来了，不过很长，所以不单独写了，看代码里的方程
附上代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn =
2003, INF =
1e9;
int n, m, v, e, dis[maxn][maxn], c[maxn], d[maxn];
double k[maxn], dp[
2003][
2003][
2];
int main() {
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++) cin >>
k[i];
for(
int i=
1; i<=v; i++
)
for(
int j=
1; j<=v; j++
)
dis[i][j] =
INF;
int x, y, z;
for(
int i=
1; i<=e; i++
) {
scanf("%d%d%d", &x, &y, &
z);
dis[x][y] = dis[y][x] =
min(z, dis[x][y]);
}
for(
int s=
1; s<=v; s++
)
for(
int i=
1; i<=v; i++
)
for(
int j=
1; j<=v; j++
)
if(dis[i][j] >= dis[i][s] +
dis[s][j])
dis[i][j] = dis[i][s] +
dis[s][j];
for (register
int i =
1; i <= v; i++
)
dis[i][i] = dis[i][
0] = dis[
0][i] =
0;
for (register
int i =
0; i <= n; i++
)
for (register
int j =
0; j <= m; j++
)
dp[i][j][0] = dp[i][j][
1] =
INF;
dp[1][
0][
0] = dp[
1][
1][
1] =
0;
for(
int i=
2; i<=n; i++
) {
dp[i][0][
0] = dp[i -
1][
0][
0] + dis[c[i -
1]][c[i]];
for(
int j=
1; j<=m; j++
) {
dp[i][j][0] =
min (
dp[i-
1][j][
1] +
dis[c[i-
1]][c[i]] * (
1.0-k[i-
1]) +
dis[d[i-
1]][c[i]] * k[i-
1],
dp[i-
1][j][
0] +
dis[c[i-
1]][c[i]]
);
dp[i][j][1] =
min (
dp[i-
1][j-
1][
1] +
dis[d[i-
1]][d[i]] * k[i-
1] * k[i] +
dis[d[i-
1]][c[i]] * k[i-
1] * (
1-k[i]) +
dis[c[i-
1]][d[i]] * (
1-k[i-
1]) * k[i] +
dis[c[i-
1]][c[i]] * (
1-k[i-
1]) * (
1-
k[i]),
dp[i-
1][j-
1][
0] +
dis[c[i-
1]][d[i]] * k[i] +
dis[c[i-
1]][c[i]] * (
1-
k[i])
);
}
}
double ans =
1e17;
for(
int i=
0; i<=m; i++
)
ans = min(ans, min(dp[n][i][
0], dp[n][i][
1]));
printf("%.2lf", ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9606722.html
相关资源：数据结构—成绩单生成器
