NOIP2016 提高组 换教室 (BZOJ 4720)

发布于 2017-04-19  301 次阅读


题目链接:BZOJ:http://www.lydsy.com/JudgeOnline/problem.php?id=4720  洛谷:https://www.luogu.org/problem/show?pid=1850

题意:给一张无向图,有 n 个时间,对于第 i 个时间,要去地点 c[i],每条边都有一个权值。同时,每个时间还有一个备用地址 d[i],有 m 次申请机会,通过几率为 k[i],问总消耗的期望是多少...


本题考试的时候连 floyd 都不会... 强行水了前几个点 qwq 现在一看好水,结果一发 32pts...

坑有点多,调了 1h30min 左右...  我还是太弱了 qwq 具体犯过的智障错误有:inf 开小了,inf 开大了, 数组开小了, 数组开大了等......

下面是正式题解:

首先用 floyd 预处理出两点距离 dis 备用,我们考虑怎么转移...

dp[i][j][0/1] 表示目前时间点为 i,申请了 j 次,且本次不通过/通过

式子很好想,但是需要考虑好多情况...

dp[i][j][0]=min(上次没有申请,上次申请了通过+不通过)

dp[i][j][1]=min(上次没有申请,通过通过+不通过通过+通过不通过+不通过不通过)

具体式子在代码里...

 


一个非常弱的准退役OIER