传送门。
前置知识
区间 dp。
题意
一个周长为 \(L\) 的圆，在初始点的顺时针方向依次排列着 \(N\) 物品，第 \(i\) 个物品在顺时针 \(X_i\) 米处，可以在 \(T_i\) 前收集到这个物品。
此时，从初始点出发，时间为 \(0\)，允许顺时针或逆时针移动，问最多可以收集到多少物品。
分析
首先考虑部分分，我们不可能在两个结点左右徘徊，假如现在开始行走，那么我们至少要一个方向走到一个结点，否则我们就在徘徊的时候就是在浪费时间。
这也就代表了，我们所行走的路程，必然是两个结点中间的这一段连续的空间，而由于我们是一个圆上的区间，因此我们考虑使用区间 DP 并且拆环成链来解决。
这时，我们又有了一个问题，那就是我们的物品只能在 \(T_i\) 的时间内到达才可以拾取当前物品，我们该如何维护选取的个数与时间。
其实问题远没有想的那么麻烦，我们从数据范围出手，\(n\le 200\)，在时间复杂度上，支持 \(n^3\) 以至于玄学 \(n^4\)，空间上，我们 \(1GB\) 足以 \(n^3\)，因此直接再开一维来维护获取的物品量。
总结一下我们的 dp 数组：\(f_{L,R,k,0/1}\) 表示当前的最左曾到达 \(L\)，最右到达 \(R\)，获取了 \(k\) 个物品，当前位于左端点亦或是右端点。
考虑转移，对于 \(f_{L,R,k,0/1}\)，必然是从 \(f_{L+1,R}\) 转移而来，只需要左走左，右走右，维护是否可以拾取，在将左右互相维护即可。
下面给出转移：
for(int k=0; k<=n; ++k) {
int t=f[L+1][R][k][0]+lenth(a[L+1].x,a[L].x),opt=k+(t<=a[L].t);
f[L][R][opt][0]=min(f[L][R][opt][0],t);
f[L][R][opt][1]=min(f[L][R][opt][1],f[L][R][opt][0]+lenth(a[R].x,a[L].x));
t=f[L][R-1][k][1]+lenth(a[R].x,a[R-1].x),opt=k+(t<=a[R].t);
f[L][R][opt][1]=min(f[L][R][opt][1],t);
f[L][R][opt][0]=min(f[L][R][opt][0],f[L][R][opt][1]+lenth(a[R].x,a[L].x));
}
for(int k=0; k<=n; ++k) if(f[L][R][k][0]<INF||f[L][R][k][1]<INF) ans=max(ans,k);
对于初始化，直接走 \(n\) 或 \(n+1\)（拆换成链）即可。
总结起来这道题还是比较简单的，是一道区间 dp 的比较常规的题。