\(\mathscr{Problem}\)
给定一个周长为 \(M\) 的圆，从原点出发，有 \(N\) 个邮票展台，编号为 \(1\) 到 \(N\) ，第 \(i\) 个展台在顺时针 \(X_i\) 米处，并且在 \(T_i\) 秒时关闭。
现在 JOI 君在原点，他每一秒可以移动一米，并且他可以顺时针或者逆时针移动，他到达每一个未关闭的邮票展台时可以收集一枚邮票。
JOI 君想问，他最多能收集多少枚邮票？
数据范围
- Subtask 1（5 pts）：\(N \le 12\)，\(M \le 200\)，\(X_i \le 200\)。
- Subtask 2（10 pts）：\(N \le 15\)。
- Subtask 3（10 pts）：\(M \le 200\)，\(T_i \le 200\)。
- Subtask 4（75 pts）：无特殊限制。
对于 \(100\%\) 的数据：
- \(1 \le N \le 200\)。
- \(2 \le M \le 10^9\)。
- \(1 \le X_i<L\)。
- \(X_i < X_{i+1}\)。
- \(0 \le T_i \le 10^9\)。
\(\mathscr{Solution}\) \(0\)
进行全排列枚举访问展台的顺序，再模拟行走的过程判断能收集多少枚邮票。
时间复杂度 \(Θ(N×N!)\) 。并不能通过 Subtask 1。
\(\mathscr{Solution}\) \(1\)
考虑 \(N\) 较小，进行状压 \(DP\) 。
设 \(dp[S][i][t]=\) 访问过的展台的集合 \(S\) ，现在在展台 \(i\) ，当前时间为 \(t\) 时邮票的最大值。
状态数 \(Θ(2^NNT)\) ,转移 \(Θ(N)\) 。可以通过 Subtask 1。
命运的分叉路
考虑 \(DP\) 状态的瓶颈。
其一在于 \(Θ(2^N)\) 的第一维集合状态，与 \(Θ(T)\) 的第三维时间。
两个瓶颈也引出我们今天的主题——如何设计DP状态？
\(\mathscr{Solution}\) \(2\)
考虑 \(T\) 很大时，\(DP\) 数组的值却不超过 \(N\) ，一个经典技巧是交换下标与值。
\(dp[S][i][k]=\) 访问过的展台的集合 \(S\) ，现在在展台 \(i\) ，当前邮票数量为 \(k\) 时花费时间的最小值。
统计答案时枚举值不为 \(INF\) 的下标 \(k\) 即可。可以通过 Subtask 2。
\(\mathscr{Solution}\) \(3\)
\(N\) 较大时，无法用 \(S\) 来表示已经过的展台。
考虑一次行走从一个展台到另一个展台，它们之间的展台一定是全部都选，因为收集邮票并不需要花费时间。即 \(S\) 是一个连续的区间，可以用区间的左端点 \(L\) 与右端点 \(R\) 来代表整个区间。考虑到行走的转折点与更新答案的点都一定是存在展台的点。故将 \(L\) 与 \(R\) 代表区间最左的展台与最右的展台。JOI 君一定在区间的左端点或右端点。
\(dp_l[i][j][t]=\) 当前区间的左端点为 \(i\) ,右端点为 \(j\) ，现在在左端点时，花费时间为 \(t\) 的邮票数量最大值。
\(dp_r[i][j][t]=\) 当前区间的左端点为 \(i\) ,右端点为 \(j\) ，现在在右端点时，花费时间为 \(t\) 的邮票数量最大值。
状态数 \(Θ(N^2T)\) ，转移 \(Θ(1)\) 。可以通过 Subtask 3。
\(\mathscr{Solution}\) \(4\)
将前面两种优化结合：
\(dp_l[i][j][k]=\) 当前区间的左端点为 \(i\) ,右端点为 \(j\) ，现在在左端点时，邮票数量为 \(k\) 时，花费时间的最小值。
\(dp_r[i][j][k]=\) 当前区间的左端点为 \(i\) ,右端点为 \(j\) ，现在在右端点时，邮票数量为 \(k\) 时，花费时间的最小值。
为了便于实现，考虑将环从原点断开，设 \(dp[i][j][k]\) 的区间为区间 \([0,i]\) 与区间 \([j,m]\) 的并集。再设 \(X_{n+1}=m\) ，为了便于计算距离。转移时让 \(i<j-1\) 就不会重复计算贡献。
状态数 \(Θ(N^3)\) ，转移 \(Θ(1)\) 。满分。
\(\mathscr{Code}\)
#include<bits/stdc++.h>
using namespace std;
const int N=2e2+9;
const int INF=0x3f3f3f3f;
void maxx(int &x,int y){if(y>x) x=y;
}
void minn(int &x,int y){if(y<x) x=y;
}
int n,m,x[N],t[N],dpl[N][N][N],dpr[N][N][N],ans;
int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>x[i];x[n+1]=m;for(int i=1;i<=n;i++) cin>>t[i];memset(dpl,0x3f,sizeof dpl);memset(dpr,0x3f,sizeof dpr);dpl[0][n+1][0]=dpr[0][n+1][0]=0;for(int i=0;i<=n;i++)for(int j=n+1;j>=1;j--)for(int k=0;k<=n;k++){if(i>=j-1) continue;if(dpl[i][j][k]!=INF){int now=dpl[i][j][k],tl=x[i+1]-x[i],tr=m-(x[j-1]-x[i]);minn(dpl[i+1][j][k+(now+tl<=t[i+1])],dpl[i][j][k]+tl);minn(dpr[i][j-1][k+(now+tr<=t[j-1])],dpl[i][j][k]+tr);}if(dpr[i][j][k]!=INF){int now=dpr[i][j][k],tl=m-(x[j]-x[i+1]),tr=x[j]-x[j-1];minn(dpl[i+1][j][k+(now+tl<=t[i+1])],dpr[i][j][k]+tl);minn(dpr[i][j-1][k+(now+tr<=t[j-1])],dpr[i][j][k]+tr);}}for(int i=0;i<=n;i++) for(int j=0;j<=n+1;j++) for(int k=0;k<=n;k++)if(dpl[i][j][k]!=INF||dpr[i][j][k]!=INF) maxx(ans,k);cout<<ans;return 0;
}