题目描述:
略
思路:
floyd求最短路+概率dp
先用floyd求出每两个点间的最短距离
用d(i,j,0/1)表示在前i个时间段, 换教室j次, 第i次换或不换的最小数学期望
答案为min{d(n,j,0/1)}(0<=j<=m)
转移方程见代码
代码:
1 |
|
略
floyd求最短路+概率dp
先用floyd求出每两个点间的最短距离
用d(i,j,0/1)表示在前i个时间段, 换教室j次, 第i次换或不换的最小数学期望
答案为min{d(n,j,0/1)}(0<=j<=m)
转移方程见代码
1 | #include <iostream> |