UVA 12230 Crossing Rivers

嘟嘟嘟

虽然分类是期望dp，不过好像是最水的

因为在陆地上的时间和概率是固定的，所以只用考虑过河的期望时间。

对于一条河p, l, v，p好像没什么用……不管了，首先期望时间我觉得可以这么算：期望时间=期望距离 / 速度，又因为船停的位置和方向都是等概率随机的，所以期望的距离就是平均距离，很显然最长的距离是3L，最短是L，那么平均距离就是2L，期望时间就是2L / v。

初始化ans = d,那么每一次ans = ans - L + 2L / v.

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<vector>

 #include<stack>

 #include<queue>

 using namespace std;

 #define enter puts("")

 #define space putchar(' ')

 #define Mem(a) memset(a, 0, sizeof(a))

 typedef long long ll;

 typedef double db;

 const int INF = 0x3f3f3f3f;

 const db eps = 1e-;

 //const int maxn = ;

 inline ll read()

 {

     ll ans = ;

     char ch = getchar(), last = ' ';

     while(!isdigit(ch)) {last = ch; ch = getchar();}

     while(isdigit(ch)) {ans = ans *  + ch - ''; ch = getchar();}

     if(last == '-') ans = -ans;

     return ans;

 }

 inline void write(ll x)

 {

     if(x < ) x = -x, putchar('-');

     if(x >= ) write(x / );

     putchar(x %  + '');

 }

 int n, d, cnt = ;

 int main()

 {

     while(scanf("%d%d", &n, &d) && (n || d))

     {

         db ans = d;

         for(int i = ; i <= n; ++i)

         {

             int p = read(), l = read(), v = read();

             ans = ans - l +  * (db)l / (db)v;

         }

         printf("Case %d: %.3lf\n\n", ++cnt, ans);

     }

     return ;

 }