类似思考

看到这道题会想到 P1220 关路灯，是一个 区间 DP ，这类区间 DP 是不需要枚举断点的，一般的转移方程是 $f_{i,j}=\min(f_{i+1,j},f_{i,j-1})$ 具体需要看情况而加减或乘除某个数。

---

题目分析

第一步：破环为链

在一个环上，要转换成线性的，那么我们先要 破环为链 ，相当于更简化的枚举断点。

还要将起点加入到这个数组中，将爆炸时间赋值为 $-1$ 就不会把它考虑最终的答案中。

---

第二步：定义状态

我们先考虑一般的二维数组 $f_{i,j}$ 为区间 $i,j$ 中最多能取几个。因为雕像会爆炸，那么我们不一定能将 $i,j$ 这个区间的所有雕像都拿完，没有办法计算能取几个，所以二维的不行。我们要考虑在 $i,j$ 这个区间中到底取了几个。从而来枚举这个个数。

那么我们加上一维变成 $f_{i,j,k}$ 表示在区间 $i,j$ 中取 $k$ 个最少需要的时间。显然通过枚举 $k$ 最后再判断能否成立。

但是在一个区间中位置有两种情况，一种是在区间的最左端，一种是在区间的最右端。用 $0/1$ 分别表示最左或最右。

最终定义的状态是 $f_{i,j,k,0/1}$ 表示在区间 $i,j$ 中最后到区间的最左端或最右端时拿 $k$ 个雕像最少需要的时间。

---

第三步：寻找状态转移方程

($a_i.x$ 表示点 $i$ 的位置，$a_i.t$ 表示点 $i$ 的爆炸时间) 首先我们考虑如果到达区间 $i,j$ 两端时，雕像已经爆炸的情况。那么取的个数相对于区间 $i+1,j$ 和 $i,j-1$ 不变,也就是 $k$ 的值不变，由此推出：

第一个:$f_{i,j,k,0}=\min(f_{i,j,k,0},f_{i+1,j,k,0}+a_{i+1}.x-a_i.x)$

第二个:$f_{i,j,k,0}=\min(f_{i,j,k,0},f_{i+1,j,k,1}+a_{j}.x-a_i.x)$

第三个:$f_{i,j,k,1}=\min(f_{i,j,k,1},f_{i,j-1,k,1}+a_{j}.x-a_{j-1}.x)$

第四个:$f_{i,j,k,1}=\min(f_{i,j,k,1},f_{i,j-1,k,0}+a_{j}.x-a_{i}.x)$

但是还有其他情况。当到达区间 $i,j$ 两端时，雕像没有爆炸的情况。那么取的个数相对于区间 $i+1,j$ 和 $i,j-1$ 增加了一个，也就是 $k$ 的值增加了 $1$。

由此推出（如果爆炸了就不考虑下列情况）：

第五个:

当 $(f_{i+1,j,k-1,0}+a_{i+1}.x-a_i.x)\leq a_i.t$ 时

$f_{i,j,k,0}=\min(f_{i,j,k,0},f_{i+1,j,k-1,0}+a_{i+1}.x-a_i.x))$

第六个:

当 $(f_{i+1,j,k-1,1}+a_j.x-a_i.x)\leq a_i.t$ 时

$f_{i,j,k,0}=\min(f_{i,j,k,0},f_{i+1,j,k-1,1}+a_j.x-a_i.x)$

第七个:

当 $(f_{i,j-1,k-1,1}+a_j.x-a_{j-1}.x)\leq a_j.t$ 时

$f_{i,j,k,1}=\min(f_{i,j,k,1},f_{i,j-1,k-1,1}+a_j.x-a_{j-1}.x)$

第八个:

当 $(f_{i,j-1,k-1,0}+a_j.x-a_i.x)\leq a_j.t$ 时

$f_{i,j,k,1}=\min(f_{i,j,k,1},f_{i,j-1,k-1,0}+a_j.x-a_i.x)$

---

第四步： 起点（初始化）

对于这道题，起点是确定的，但是我们要注意初始化的问题。

显然我们在枚举 $k$ 的过程中发现需要用到 $k$ 为 $0$ 时的区间时间。那么我们将 $k$ 为 $0$ 时的所有区间赋值。如果在左端点值为：周长 $-a_i.x$,如果在右端点值为：$a_j.x-$ 周长。（切记，虽然取得个数为 $0$，但是也需要将整个区间走完，不能取最小值）

还要将 $f$ 数组赋成最大值。从而为取最小值和判断是否成立做准备。但是要将原点的都赋为 $0$。

---

第五步：终点

这道题的终点比较特别，是判断时间是否小于最大值而确定这个 $k$ 是否能取到。如果能取到就更新 $ans$ 的最大值，最后输出 $ans$。

---

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=410;
int n,m,f[N][N][210][2],ans;//定义状态
struct que
{
	int x,t;
}a[N];//距离和爆炸时间
signed main(){
	cin>>n>>m;//个数和周长
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x;
		a[i+n+1].x=a[i].x+m;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].t;
		a[i+n+1].t=a[i].t;
	}//破环为链
	memset(f,0x3f,sizeof(f));
	a[n+1].x=m,a[n+1].t=-1e18,f[n+1][n+1][0][0]=0,f[n+1][n+1][0][1]=0;//加入起点
	for(int j=n+1;j<=2*n+1;j++)
	{
		for(int i=n+1;j&&j-i<=n;i--)
		{
			f[i][j][0][0]=m-a[i].x;
			f[i][j][0][1]=a[j].x-m;
		}
	}//初始化
	for(int len=1;len<=n;len++)//从小往大，按顺序
	{
		for(int i=1;i<=n+1;i++)//枚举左端点
		{
			int j=i+len;
			for(int k=1;k<=len;k++)//枚举个数
			{
				int s1;
				f[i][j][k][0]=min(f[i][j][k][0],f[i+1][j][k][0]+a[i+1].x-a[i].x);
				s1=f[i+1][j][k-1][0]+a[i+1].x-a[i].x;
				if(s1<=a[i].t)f[i][j][k][0]=min(f[i][j][k][0],s1);
				f[i][j][k][0]=min(f[i][j][k][0],f[i+1][j][k][1]+a[j].x-a[i].x);
				s1=f[i+1][j][k-1][1]+a[j].x-a[i].x;
				if(s1<=a[i].t)f[i][j][k][0]=min(f[i][j][k][0],s1);
				f[i][j][k][1]=min(f[i][j][k][1],f[i][j-1][k][1]+a[j].x-a[j-1].x);
				s1=f[i][j-1][k-1][1]+a[j].x-a[j-1].x;
				if(s1<=a[j].t)f[i][j][k][1]=min(f[i][j][k][1],s1);
				f[i][j][k][1]=min(f[i][j][k][1],f[i][j-1][k][0]+a[j].x-a[i].x);
				s1=f[i][j-1][k-1][0]+a[j].x-a[i].x;
				if(s1<=a[j].t)f[i][j][k][1]=min(f[i][j][k][1],s1);
				if(f[i][j][k][0]<1e15)ans=max(ans,k);
				if(f[i][j][k][1]<1e15)ans=max(ans,k);//判断是否成立
			}//状态转移
		}
	}
	cout<<ans;
	return 0;
}