Input
第一行四个整数n,m,v,e。n表示这个学期内的时间段的数量;m表示牛牛最多可以申请更换多少节课程的教室;
v表示牛牛学校里教室的数量;e表示牛牛的学校里道路的数量。
第二行n个正整数,第i(1≤i≤n)个正整数表示c,,即第i个时间段牛牛被安排上课的教室;保证1≤ci≤v。
第三行n个正整数,第i(1≤i≤n)个正整数表示di,即第i个时间段另一间上同样课程的教室;保证1≤di≤v。
第四行n个实数,第i(1≤i≤n)个实数表示ki,即牛牛申请在第i个时间段更换教室获得通过的概率。保证0≤ki≤1。
接下来e行,每行三个正整数aj,bj,wj,表示有一条双向道路连接教室aj,bj,通过这条道路需要耗费的体力值是Wj;
保证1≤aj,bj≤v,1≤wj≤100。
保证1≤n≤2000,0≤m≤2000,1≤v≤300,0≤e≤90000。
保证通过学校里的道路,从任何一间教室出发,都能到达其他所有的教室。
保证输入的实数最多包含3位小数。
Output
输出一行,包含一个实数,四舎五入精确到小数点后恰好2位,表示答案。你的
输出必须和标准输出完全一样才算正确。
测试数据保证四舎五入后的答案和准确答案的差的绝对值不大于4*10^-3。(如果你不知道什么是浮点误差,这段话可以理解为:对于大多数的算法,你可以正常地使用浮点数类型而不用对它进行特殊的处理)
Sample Input
3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1
Sample Output
2.80
这道题也可以算得上是经典了。当时考NOIP碰到这道题，当时还壮志满怀，很长的一道题（至少当时看来是这样的）很快就被我读完了，发现可以分成三份：课程、教室，申请、概率，道路、耗费体力最少。
当时，我的很多同学见此题太长，就根本没有看。此题虽然沾期望，但其实很简单。
----------因为后面扯的东西比较多，就在这里讲一下思路。----------
我们这样开数组：f[2][2][M]，第一维枚举课程但可以“滚动”(cur)，第二位判断在第i门课程是否提交申请，第三维给现在已申请的课程计一下数。空间是O（M）的，时间是O（NM）的，最后输出f[cur][j][p](j=0,1; p=0,1,...,m)
这样，我们可以考虑转移。一个课程如果没有申请，那就是100%的“纯爷们儿”教室c。但如果申请了呢？可以YY一下薛定谔的猫，有概率的事件可以当做对立统一的个体。也就是说一个课程如果申请了，就可以看做k[i]个d教室和1-k[i]个c教室，实际转移时思考一下即可。
关于方程可以看看我的代码（本文末尾）。
----------好的，思路讲完了。我可以开始扯了。----------
当时我高兴极了，发现可以把课程当做i，把申请数当做j，把此时是否申请当0/1。当时才学了DP，只会背包（还是最简单的）和floyd，什么LIS、数位、状压（NOIPD2T3ANGRYBIRD）、树形都不知道，更不用说什么概率和期望了……然而就是考了。YJQ表示，不要再逼我吃键盘了。
关于吃键盘一事，都是因为——YJQ说NOIP绝对不考期望DPNOIP这么水的考试怎么可能考这种东西写个暴力就A题的比赛要是考了这种东西我就直播吃键盘……YJQ其实是一个很谨慎的人，不像lemonoil每天立下flag要直播吃掉∞个键盘。
“兜售巧克力味键盘了喂！专门为立flag死掉的人设计的喂~~~”
所以就是这样的。然而我当时就是想到了如何去做，虽然现在看完题就可以切过去。因为当时我既会背包，也会floyd。不过，天有不测风云，我当时的代码实现能力实在是太弱了……
弱到什么地步？也就是说，我发现当时k数组定义的是int类型……也许，质问当时的我，我还会义愤填膺地说，int不就是数么整数是数小数难道不是数么？！
呃呃呃呃呃。
然而，当我现在做到这道题时，当我已经“掌握”了概率与期望的时候，还是WA。
恩。请来客忽略我的强制调剂（eyeprotect）。一边调，一会儿AC，一会儿又WA的体验真的是第一回碰到。更令人惊奇的是，中间居然还有CE，让人颇为尴尬。要是NOIP也这样，那恐怕就只有再见OI了。
最后突然发现，卡了这么久竟是这两个原因。
1.memset(dis,65,sizeof(dis))很明显是错的，因为在floyd内部，dis+dis会跳负。应将65改成63或127/2。
2.这个地方才真正调了我很久，这个地方是让人非常尴尬的。DP中常常有x=std::min(x,y);的语句出现，但我在修改时只把第一个x改对了……所以说需要有#define smin(x,y) x=std::min(x,y)啊（YYF、mcfx等大佬强力推荐）！
最后挂一波代码吧。
1、全排列 NOJ 1103
2、while 注意点and do While
3、Python while 循环使用实例
4、螺旋方阵
5、Elasticsearch 集群配置
1 /************************************************************** 2 Problem: 4720 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:1960 ms 7 Memory:1292 kb 8 ****************************************************************/ 9 10 #define PN "classroom" 11 #include <cstdio> 12 #include <cstring> 13 #include <algorithm> 14 #define smin(x,y) x=std::min(x,y) 15 const int N = 2000+50; 16 const int M = 2000+50; 17 const int V = 300+10; 18 int n, m, v, e, c[N], d[N], dis[V][V], cur=0; 19 double k[N], f[2][2][M]; 20 21 int main() { 22 scanf("%d%d%d%d",&n,&m,&v,&e); 23 for( int i = 1; i <= n; i++ ) scanf("%d",&c[i]); 24 for( int i = 1; i <= n; i++ ) scanf("%d",&d[i]); 25 for( int i = 1; i <= n; i++ ) scanf("%lf",&k[i]); 26 memset(dis,63,sizeof(dis)); 27 for( int i = 1,a,b,w; i <= e; i++ ) { 28 scanf("%d%d%d",&a,&b,&w); 29 if(dis[a][b]>w) dis[a][b]=dis[b][a]=w; 30 } 31 for( int i = 1; i <= v; i++ ) dis[i][i]=0; 32 for( int p = 1; p <= v; p++ ) 33 for( int i = 1; i <= v; i++ ) 34 for( int j = 1; j <= v; j++ ) 35 if (dis[i][j]>dis[i][p]+dis[p][j]) 36 dis[i][j]=dis[i][p]+dis[p][j], 37 dis[j][i]=dis[i][j]; 38 memset(f[cur],127,sizeof(f[cur]));f[cur][0][0]=f[cur][1][1]=0; 39 for( int i = 2; i <= n; i++ ) { 40 cur^=1;memset(f[cur],127,sizeof(f[cur])); 41 for( int p = 0; p <= m; p++ ) { 42 smin(f[cur][0][p],f[cur^1][1][p]+k[i-1]*dis[c[i]][d[i-1]]+(1-k[i-1])*dis[c[i]][c[i-1]]); 43 smin(f[cur][0][p],f[cur^1][0][p]+dis[c[i]][c[i-1]]); 44 smin(f[cur][1][p+1],f[cur^1][1][p]+k[i]*k[i-1]*dis[d[i]][d[i-1]]+(1-k[i])*k[i-1]*dis[c[i]][d[i-1]]+k[i]*(1-k[i-1])*dis[d[i]][c[i-1]]+(1-k[i])*(1-k[i-1])*dis[c[i]][c[i-1]]); 45 smin(f[cur][1][p+1],f[cur^1][0][p]+k[i]*dis[d[i]][c[i-1]]+(1-k[i])*dis[c[i]][c[i-1]]); 46 } 47 } 48 double ans=2000000000; 49 for( int j = 0; j <= 1; j++ ) 50 for( int p = 0; p <= m; p++ ) 51 ans=std::min(ans,f[cur][j][p]); 52 printf("%.2lf\n",ans); 53 return 0; 54 } 55NOIP第一道期望DP 优质内容筛选与推荐>>
1、全排列 NOJ 1103
2、while 注意点and do While
3、Python while 循环使用实例
4、螺旋方阵
5、Elasticsearch 集群配置