1 条题解
-
0
动态规划。
先考虑最简单的，设dp[i,j,k]表示第i时间在(j,k)处滑行的最长距离。
dp[i,j,k]=max{dp[i-1,j’,k’]+1,dp[i-1,j,k]}
复杂度是O(TMN)，可以过50%的数据。
数据规模很具有提示性，考虑从每一段时间入手。
设dp[i,j,k]表示在第i段时间末在(j,k)处滑行的最长距离。
dp[i,j,k]=max{dp[i-1,j0,k0],dp[i-1,j1,k1]+1,dp[i-1,j2,k2]+2,..,dp[i-1,jn,kn]+n}
时间复杂度仍然是O(TMN)。
以一个方向为例，在求A的时候，需要统计黄色框中的最大值，而求B的时候需要统计绿色框中的最大值。
在求A的过程中统计红色框中的最大值，设为op，则在求B的时候，只需要考虑op和C处，大大减少了重复运算。
如果绿色框中的最大值不在B，那么op可以继续使用，否则需要重新计算op。
这样复杂度相比与O(TMN)要小很多，但并不是确切的O(KMN)，因为要不时的重新计算op。但是已经可以过所有数据了。.
看了Amber的blog，发现自己写的垃圾了。
在计算dp的时候用“单调队列”，所谓的单调队列，就是维护一个这样的队列。
每个点记录两个值：
time-该点加入队列的时间（对于本题就是该点的位置）
value-该点的权值
维护该队列中所有点的time和value均单调（对于本题value递减，time递增）。
该队列的操作有：
插入一个点(t,v)：将队列尾<v的点删除，将该点加入队尾。
统计t时队列中的最大权：将队头<t的点删除，输出队头的点。
每个点加入和删除队列最多1次，这样就不需要重新计算op，复杂度就是O(KMN)了。