Fork me on GitHub

[题解] Noip2016D1T3 换教室

一道被天天爱跑步抢尽了风头的最没有排面的$T3…..$

说实话,这道题我刚开始是不会的,然后我看了
L_Y_T大爷的$Blog$之后才恍然大悟($Blog$写的很好,赞一个)
先安利完$Blog$再说
L_Y_T大爷的Blog

看了$Blog$之后,突然发现,这东西要求的概率知识点我都是会的,只是DP式子想不出来而已$qaq…$(我好菜啊)

因为题目中说,我们最多可以换$m$次,而题目中说的你只能在开始之前选择方案的说法完全没用,毕竟谁会知道你是预测了未来呢(逃

然后,因为有$n$个课程,所以我们设$f[i][j][0/1]$来表示第i个点,第j次换,换不换

然后我们分情况来表示转移:
每个教室分为两种情况

1.换
2.不换
这个是挺平常的
然后复杂在换与不换的分情况上了~~~
不换:
不换是分为这样几种情况:
上一个也不换 , 上一个换 且成功,上一个换但失败
同理,换也有好多种情况:
上一个点不换,这个点失败
上一个点不换,这个点成功
上一个点换成功,这个点成功
上一个点换成功,这个点失败
上一个点换失败,这个点成功
上一个点换失败,这个点也失败

然后方程好复杂的,是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
上一点不换:f[i-1][j-1][0]
这一点换
1.失败
消耗体力: dis[c[i-1]][c[i]]
分析: 由于上一个点不换,所以上一个点一定是在c[]中的;假定这次失败,那么这次也只能去c[]中的教室;
2.成功
消耗体力: dis[c[i-1]][d[i]]
分析: 由于上一个点不换,所以上一个点一定是在c[]中的;假定这次成功,那么这次能去d[]中的教室;
那么,失败的概率是1-k[],成功的概率是k[].
综上,这种情况就是:
f[i-1][j-1][0]+dis[c[i-1]][d[i]]*k[i]+dis[c[i-1]][c[i]]*(1.0-k[i])

同理,上一点换,这一点换
1.上一点失败,这一点失败(以后省一点哈)
消耗体力: dis[c[i-1]][c[i]]
概率:都失败这运气也没谁了!!!! 概率:(1.0-k[i-1])*(1.0-k[i])
2.失败,成功
消耗体力: dis[c[i-1]][d[i]]
概率 : (1.0-k[i-1])*k[i]
3.成功,失败
消耗体力 : dis[d[i-1]][c[i]]
概率: k[i-1]*(1.0-k[i])
4.成功,成功
消耗体力: dis[d[i-1]][d[i]]
概率: k[i-1]*k[i]

然后对于不换的方程:

1
2
f[i][j][0] = min(f[i-1][j][0]+dis[c[i-1]][c[i]],
f[i-1][j][1]+dis[c[i-1]][c[i]]*(1.0-k[i-1])+dis[d[i-1]][c[i]]*k[i-1]) ;

之前需要Floyd预处理一下,然后就好啦
(这道题的确比天天爱跑步简单23333)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

const int N = 2050;
const int M = 350;

int n , m , v , e;
int c[N] , d[N] ;
double G[M][M] , f[N][N][2];
double k[N];

template < class T >
inline T min ( T x , T y ) {
return x < y ? x : y;
}

int main ( void ) {
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++ )
scanf ( "%lf" , &k[i] );
for ( int i = 1 ; i <= v ; i++ )
for ( int j = 1 ; j <= v ; j++ )
G[i][j] = 0x3f3f3f3f;
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 0 ; j <= m ; j++ )
f[i][j][0] = f[i][j][1] = 0x3f3f3f3f;
for ( int i = 1 ; i <= v ; i++ )
G[i][i] = 0 ;
for ( int i = 1 ; i <= e ; i++ ) {
int x , y;
double z;
scanf ( "%d%d%lf" , &x , &y , &z );
if ( G[x][y] > z )
G[x][y] = G[y][x] = z;
}
for ( int l = 1 ; l <= v ; l++ )
for ( int i = 1 ; i <= v ; i++ )
for ( int j = 1 ; j <= v ; j++ )
G[i][j] = min ( G[i][j] , G[i][l] + G[l][j] );
f[1][0][0] = f[1][1][1] = 0.0000;
for ( int i = 2 ; i <= n ; i++ )
for ( int j = 0 ; j <= min ( i , m ) ; j++ ) {
f[i][j][0] = min ( f[i - 1][j][0] + G[c[i - 1]][c[i]] , f[i - 1][j][1] + G[c[i - 1]][c[i]]
* ( 1.0 - k[i - 1] ) + G[d[i - 1]][c[i]] * k[i - 1] );
if(j >= 1) {
f[i][j][1] = min ( f[i - 1][j - 1][0] + G[c[i - 1]][d[i]] * k[i] + G[c[i - 1]][c[i]] * ( 1.0 - k[i] ) ,
f[i - 1][j - 1][1] + G[c[i - 1]][c[i]] * ( 1.0 - k[i - 1] ) * ( 1.0 - k[i] ) + G[c[i - 1]][d[i]]
*k[i] * ( 1.0 - k[i - 1] ) + G[d[i - 1]][c[i]] * k[i - 1]* ( 1.0 - k[i] ) + G[d[i - 1]][d[i]] * k[i - 1] * k[i] );
}
}
double ans = 0x7fffffff;
for ( int i = 0 ; i <= m ; i++ )
for ( int j = 0 ; j <= 1 ; j++ )
ans = min ( ans , f[n][i][j] );
printf ( "%.2lf\n" , ans ) ;
return 0 ;
}

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[题解] Noip2016D1T3 换教室

文章作者:兮水XiShui丶

发布时间:2018年11月02日 - 11:11

最后更新:2019年10月21日 - 11:10

原始链接:http://krrrr.top/2018/11/02/换教室题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。