对于前30%30\%30%的数据,暴力搜索以每一个平台为终点的最大长度再输出最大值即可。
考虑使用动态规划,dp[i][j]dp[i][j]dp[i][j]表示走到第iii行第jjj列的平台时能经过的最大长度。
注意到状态只能从低处到高处单向转移,可推出状态转移方程:
加上只能从更低处转移的限制条件即可。
时间复杂度为O(mnlogmn)O(mnlog{mn})O(mnlogmn)。
改用记忆化搜索可以使时间复杂度降为O(mn)O(mn)O(mn)。
使用您的 Hydro 通用账户