对于一条河,最小期望通过时间是L/vi,这时人刚到岸边船就来了;最大的期望通过时间是3L/vi,这时人刚到岸边船刚开走。由于期望线性性,平均时间是2L/vi。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mid ((L + R) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x) {
char c = getchar(),f = 1;x = 0;
for(;c ^ '-' && !isdigit(c);c = getchar());
if(c == '-') c = getchar(),f = -1;
for(;isdigit(c);c = getchar()) x = (x<<1) + (x<<3) + (c ^ '0');
x *= f;
}
template<typename xxx>void print(xxx x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
const int maxn = 100010;
const int inf = 0x7fffffff;
const int mod = 1e9 + 7;
int n,D;
struct river{
int ks;
double L,vi;
}rv[maxn];
int main()
{
int mk = 0;
while(1) {
++mk;
read(n);read(D);
if(!n && !D) break;
int tem = 0;
double ans = 0;
for(rint i = 1;i <= n; ++i) {
scanf("%d%lf%lf",&rv[i].ks,&rv[i].L,&rv[i].vi);
ans += 2*rv[i].L/rv[i].vi;
tem += rv[i].L;
}
printf("Case %d: %0.3lf\n\n",mk,ans + D - tem);
}
return 0;
}
/*
*/
设dp[i][j]表示从(i,j)到(n,m)的期望消耗,f[i][j][0]/[1]/[2]表示不动,向右,向下的概率。
有\(dp[i][j] = f[i][j][0] * dp[i][j] + f[i][j][1] * dp[i][j+1] + f[i][j][2] * dp[i+1][j] + 2\)
整理后为\(dp[i][j] = (dp[i + 1][j] * f[i][j][2] + dp[i][j + 1] * f[i][j][1] + 2) / (1.0 - f[i][j][0])\)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mid ((L + R) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x) {
char c = getchar(),f = 1;x = 0;
for(;c ^ '-' && !isdigit(c);c = getchar());
if(c == '-') c = getchar(),f = -1;
for(;isdigit(c);c = getchar()) x = (x<<1) + (x<<3) + (c ^ '0');
x *= f;
}
template<typename xxx>void print(xxx x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
const int maxn = 1010;
const int inf = 0x7fffffff;
const int mod = 1e9 + 7;
int n,m;
double f[maxn][maxn][3];
double dp[maxn][maxn];
int main()
{
while(~scanf("%d%d",&n,&m)) {
for(rint i = 1;i <= n; ++i) {
for(rint j = 1;j <= m; ++j) {
scanf("%lf%lf%lf",&f[i][j][0],&f[i][j][1],&f[i][j][2]);//不动,向右,向下
}
}
memset(dp,0,sizeof(dp));
for(rint i = n ; i; --i) {
for(rint j = m; j; --j) {
if(f[i][j][0] == 1) {
continue;//这个点不能动,到达不了(n,m)
}
dp[i][j] = (dp[i + 1][j] * f[i][j][2] + dp[i][j + 1] * f[i][j][1] + 2) / (1.0 - f[i][j][0]);
}
}
printf("%0.3lf\n",dp[1][1]);
}
return 0;
}
/*
*/
原文:https://www.cnblogs.com/Thomastine/p/11803939.html