传送门
简单但不是很容易过的一道DP题。
状态和转移方程比较容易想。但是注意的地方很多,一不小心就WA了。
思路:首先对木板按高度从低到高排序,设置两个数组left[],right[].分别表示从第i块木板的左(右)端点到地面的最短时间。如果不能到达就用-1表示。然后从小到大进行递推,对于中间的两块木板i,j。假设如果第i块木板的左端点落在第j块木板中间,而且两块木板中间没有被隔开,那么第i块木板的左端点的最小值可以由第j块木板得到,右端点的分析和左端点相似。当然用-1表示不能到达时有一点要注意的就是改变left和right的值时,一定要注意第j块木板的左端点(或者右端点)能否到达地面也就是说是否是-1.这一点容易被忽视。
附详细注释的代码