Readme

3661.Maximum-Walls-Destroyed-by-Robots

直观上容易想到这是DP，因为每个robot只有两种决策，所以容易设计dp[i][j]表示从前往后处理，当第i个机器人选择j方向(0或者1）时能得到的最优解。转移方程也不难写出：

dp[i][0] = max(dp[i-1][1]+shoot(i,0)-overlap(i), dp[i-1][0]+shoot(i,0));            
dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + shoot(i,1);

其中shoot(i,0)表示第i号机器人朝左射击时能够击中的墙壁个数，shoot(i,1)表示第i号机器人朝右射击时能够击中的墙壁个数。overlap(i)表示当i-1号与i号机器人对射时，总共所能击中的墙壁个数。

稍微解释一下：对于dp[i][0]，它的前驱状态有两种dp[i-1][0]和dp[i-1][1]。对于前者，因为相邻两个机器人对射，所以我们要减去两者击中墙壁里重合的个数。

计算shoot(i,1)时，我们需要统计[robot[i], right]区间内有多少墙。根据规则，子弹不能击穿相邻的机器人，所以对于区间的右端点，需要与robot[i+1]之间取小。故right = min(robot[i]+distance[i], robot[i+1]). 但是此处有一个容易忽视的细节。当我们用转移方程dp[i][1] = dp[i-1][1]) + shoot(i,1)时，如果第i号机器人处恰好有墙，且恰能被第i-1号机器人射中，那么这个墙就会被计算两次。为了避免重复计算可能造成的混乱，我们约定，任何恰好在robot[i]处的墙，我们认为只是被第i号机器人击穿的。所以，shoot(i,1)的右边界应该重新定义为right = min(robot[i]+distance[i], robot[i+1]-1)，剔除掉第i+1号机器人的位置。这样转移方程就是正确的。

同理，计算shoot(i,0)时，我们需要统计在[left, robot[i]]区间内有多少个墙。同样为了避免dp[i-1][0]+shoot(i,0)可能引入的重复计数，定义区间左端点应该是left = max(robot[i]-distance[i], robot[i-1]+1)。

对于overlap(i)，它的表达式就是shoot(i-1,1) + shoot(i, 0)减去两个机器人之间的墙的个数。如果减出来的值是负数，那么返回0（因为不可能有负数个的重合）。