难以理解DP状态和转换

Question

我正在努力解决2013年JOI公开竞赛题为“观看”的问题.http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2013/watching-en.pdf删节问题陈述如下：

你有两个长度为w的小型摄像机和一个宽度为2w的大型摄像机。如果N个事件分布在一个范围内，请找到最小值w，以便所有事件都被相机覆盖。

目前，我已经明白我应该对w进行二进制搜索，但我不知道如何执行dp转换以及正确的状态是什么。

Answer 1

提示：当w被修复并且您按顺序覆盖从A_0到A_N的事件时，您可以在每个点做出两个决定：

1. 使用小型相机覆盖第一个尚未覆盖的事件（这将涵盖从Ai到Ai + w的所有点的事件）
2. 使用大型相机覆盖第一个尚未覆盖的事件（这将涵盖从Ai到Ai + 2 w的所有点的事件）。

这应该足以导出你的状态和转换。