提高B1第一讲两道题的思路总结

第一题:

思路

  1. A - 守望者的逃离
    思路总结:用dp的方式完成这道题目。难度大约为黄左右,思路不难,代码量并不复杂。
    定义1个dp数组,其中dp[i],表示第i秒最多能走多远。
    先全部用闪烁,记录最远能走多远,因为闪烁比普通前进的做法更优。同时,在最后阶段我们还需要比较步行和闪烁哪个先到终点,更新dp[i]即可完成此题。
    代入一个样例39 200 4
    首先先全部用闪烁,记录最远能走多远,模拟过程大致如下。
    dp[1]=60 , m=29
    dp[2]=120, m=19
    dp[3]=180, m=9
    dp[4]=dp[3]=180,m=9+4=13 // 较为特殊,因为m小于10了
    最后我们要判断步行和闪烁哪个先到终点。
    发现dp[4]不如等于dp[4-1]+17=dp[3]+17=197,答案为197。

第二题:

思路: B - 种树
这道题感觉洛谷题解有点复杂了,接下来要讲解的解法更好理解。
我们首先要对区间进行结构体排序,当然要证明排序的正确性,这里证明有点复杂,先这接讲结论:以右端点从小到大排序,当左端点相同时以左端点从大到小进行排序。
设d数组标记数组,1表示这个位置已经种了,0表示这个位置并没有种。每次循环先统计1的个数,在用当前需要的个数减去1的个数,从后往前种树。

第一题主要代码:

第二题主要代码:
image

仅供参考。

此话题已在最后回复的 15 天后被自动关闭。不再允许新回复。