区间dp,和UVa #1336 Fixing the Great Wall (例题9-21)类似。但数据规模太大,记忆化搜索会TLE,必须递推。
我一开始把状态设计为dp(i,j,k)表示当前已访问区间为[i,j],且站在 i (k == 0)或 j (k==1),最少还需多少时间收集全部宝藏。同时还需要一个辅助数组来记录当前已经经历的时间,来判断是否过了deadline。这个设计很臃肿。并且用记忆化搜索还行,但是递推就完全无能为力,因为无法判断到达某一宝藏时,是否已经过了deadline。
可以用对称的设计:dp(i,j,k)表示最短需要多少时间到达 [i,j,k]。对于所有的 i == j 的情况,dp......
阅读全文