111qqz的小窝

老年咸鱼冲锋!

HUST team contest #E A Mountain Road||poj 3846 (dp)

比赛的时候以为是贪心…

想了好久.

不过最后没敢写,因为没办法证明正确性,只是直觉==

最后剩下的时间给队友改另一道题了..

果然明智…

蠢的人的直觉真心不靠谱..

这题是dp

我们可以把车按照方向的不同分为A车和B车

dp[i][j][0..1]表示已经经过了a方向的i辆车,经过了b方向的j辆车,并且最后一辆车是a/b方向的情况的离开道路的时间.

 

似乎问题不大.

然后就一直wa…

wa到怀疑人生好么!!!

最后发现

问题出在!

dp数组初始化赋值成正无穷的时候,溢出啦!

然后我搜了下,发现0x7fffffff果然不是什么好东西!

以后正无穷用0x3f3f3f3f

这东西>1E9,相加不超过int

而且最重要的是,如果定义 inf = 0x3f3f3f3f

0x3f3f3f3f的每个字节都是0x3f!所以要把一段内存全部置为无穷大,我们只需要memset(a,0x3f,sizeof(a))

不要使用0x7fffffff!

不要使用0x7fffffff!

不要使用0x7fffffff!

说点什么

您将是第一位评论人!

提醒
wpDiscuz
粤ICP备18103363