这一篇的转移方程有点长
大家还是要自己推一推的
可以看出这种期望是线性的 这n个课程的答案可以拆成相邻两个课程期望的和 我们先用$floyd$求出两两点的最短路径$dis[i][j]$
令更改第$i$次课室的成功率为$p_i$
设f[i][j][0..1]
表示上完前$i$个课程 请求了$j$次 当前课程是否请求 则方程是
$f[i][j][0] = min(f[i][j][0], min(f[i - 1][j][0] + dis[lesson[i - 1][0]][lesson[i][0]], f[i - 1][j][1]+$
$ dis[lesson[i - 1][0]][lesson[i][0]] * (1 - p[i - 1]) + dis[lesson[i - 1][1]][lesson[i][0]] * p[i - 1]));$
$f[i][j][1] = min(f[i][j][1], min(f[i - 1][j - 1][0] + dis[lesson[i - 1][0]][lesson[i][0]] * (1 - p[i]) + $ $dis[lesson[i - 1][0]][lesson[i][1]] * p[i], f[i - 1][j - 1][1] + dis[lesson[i - 1][1]][lesson[i][1]] * $ $p[i] * p[i - 1] + dis[lesson[i - 1][1]][lesson[i][0]] * p[i - 1] * (1 - p[i]) + $
$dis[lesson[i - 1][0]][lesson[i][1]] * (1 - p[i - 1]) * p[i] + dis[lesson[i - 1][0]][lesson[i][0]] *$
$(1 - p[i - 1]) * (1 - p[i])));$
若觉得不适 可以看图
记得注意一些细节
比如 e和v别读反了 别问 问就是……
不然的话
(真实事件)
Author: Miku_𝓜𝓪𝓼𝓽𝓮𝓻
Date: 2021/5/29
#include <bits/stdc++.h>
using namespace std ;
int read(int x = 0,bool f = false,char ch = getchar()) {
for (;!isdigit(ch);ch = getchar()) f |= (ch == '-') ;
for (;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48) ;
return f ? ~ x + 1 : x ;
}
const int N = 2e3 + 5 , M = 3e2 + 5 ;
const double infinity = 1e17 + 1e5 ;
int n , m , Edge , v , x , y , w ;
int dis[N][N] ;
double f[N][N][2] , p[N] , ans ;
int lesson[N][2] ;
signed main() {
memset(dis,63,sizeof dis) ;
n = read() , m = read() , v = read() , Edge = read() ;
for (int i = 1 ; i <= n ; ++i ) lesson[i][0] = read() ;
for (int i = 1 ; i <= n ; ++i ) lesson[i][1] = read() ;
for (int i = 1 ; i <= n ; ++i ) scanf("%lf",p + i) ;
for (int i = 1 ; i <= Edge ; ++i )
x = read() , y = read() , w = read() , dis[x][y] = dis[y][x] = min(dis[x][y],w) ;
for (int k = 1 ; k <= v ; ++k )
for (int i = 1 ; i <= v ; ++i )
for (int j = 1 ; j <= v ; ++j )
dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]) ;
for (int i = 1 ; i <= v ; ++i ) dis[i][0] = dis[0][i] = dis[i][i] = 0 ;
for (int i = 0 ; i <= n ; ++i )
for (int j = 0 ; j <= m ; ++j )
f[i][j][1] = f[i][j][0] = infinity ;
f[1][0][0] = f[1][1][1] = 0.0 ;
for (int i = 2 ; i <= n ; ++i ) {
f[i][0][0] = f[i - 1][0][0] + dis[lesson[i - 1][0]][lesson[i][0]] ;
for (int j = 1 ; j <= min(i,m) ; ++j ) {
int fr = lesson[i - 1][0] , fr1 = lesson[i - 1][1] , to = lesson[i][0] , to1 = lesson[i][1] ;
f[i][j][0] = min(f[i][j][0], min(f[i - 1][j][0] + dis[fr][to], f[i - 1][j][1] + dis[fr][to] * (1 - p[i - 1]) + dis[fr1][to] * p[i - 1]));
f[i][j][1] = min(f[i][j][1], min(f[i - 1][j - 1][0] + dis[fr][to] * (1 - p[i]) + dis[fr][to1] * p[i], f[i - 1][j - 1][1] + dis[fr1][to1] * p[i] * p[i - 1] + dis[fr1][to] * p[i - 1] * (1 - p[i]) + dis[fr][to1] * (1 - p[i - 1]) * p[i] + dis[fr][to] * (1 - p[i - 1]) * (1 - p[i])));
}
} ans = infinity ;
for (int i = 0 ; i <= m ; ++i ) ans = min(ans,min(f[n][i][0],f[n][i][1])) ;
return printf("%.2lf\n",ans) , 0 ;
}
好长。。。
我的变量有点长 其实自己推一下挺好理解的 主体就$floyd$以及$dp$ 题刷得多了 也不会觉得很长