1 条题解

  • 0
    @ 2026-11-15 15:51:05

    题目分析

    对于前30%30\%的数据,暴力搜索以每一个平台为终点的最大长度再输出最大值即可。

    考虑使用动态规划,dp[i][j]dp[i][j]表示走到第ii行第jj列的平台时能经过的最大长度。

    注意到状态只能从低处到高处单向转移,可推出状态转移方程:

    加上只能从更低处转移的限制条件即可。

    时间复杂度为O(mnlogmn)O(mnlog{mn})。

    改用记忆化搜索可以使时间复杂度降为O(mn)O(mn)。

    • 1

    信息

    ID
    121
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者