题解 P6879 【[JOI 2020 Final] スタンプラリー 3】
虚空之灵
·
·
题解
个人博客链接
题目
题目（ja）
题目大概意思就是，沿着湖边有 n 个邮票展台，JOI君可以顺时针或者逆时针移动，每移动一个单位长度需要 1 秒，邮票展台在 T_i 时间后会被移除，问JOI君最多可以收集多少个邮票。
为什么要把仅有的日语水平用到奇怪的地方啊
（P.S. 有官方的英语翻译版为什么题都做完了才发现
题目（en）
（P.S. 洛谷上有这道题的翻译版，但是把邮票展台翻译成了黑白熊（？这是什么）
题目（zh）
思路
看到 N \leq 200 ，上手当然是动态规划。
而且可以开到三维，甚至玄学优化后的四维。
这样一来，先是想用dp数组表示能够收集到的邮票个数，但是这样一来时间就没法放进状态里（因为 T \leq 10^9 ）。于是果断看官方题解
事实上，在看到题解里关于Subtask2的解法的时候，我就瞬间悟了。
(图片版权信息：©保坂結)
（注：图上文字意思依次为：
- Exchange subscript and value
- Maximum stamps amount when elapsed time is T
- minimum time when stamps amount is k）
但是事实上之前我已经想到了可以用区间dp，这样就有了：
dp_0[l][r][k]
和
dp_1[l][r][k]
设周长为 $m$ ， $a_i$ 表示第 $i$ 个邮票展台的坐标， $t_i$ 表示第 $i$ 个邮票展台的移除时间。由于题目里的坐标是顺时针给出，对于原点顺时针方向的点，可以直接用更靠顺时针方向的点坐标与其相减得到距离，而对于逆时针方向的点，需要用总数减去个数来获取其下标，如果两个点刚好跨过原点，还需要用周长减去两者的距离才能得到移动的距离。这些关系在纸上画图推导一下就可以推出，此处不继续做详细说明。
不难发现，有如下转移：
当 $dp_0 \neq \text{INF}$ 时，对于 $dp_0$ ，设
$$tNow = dp_0[l][r][i]$$
$$t_0 = tNow+a_{n-l+1}-a_{n-l}$$
$$t_1 = tNow+m-(a_{n-l+1}-a_{r+1})$$
则：
$$
dp_0[l+1][r][i+(t_0 \leq t_{n-l})] = \min\left\{\begin{aligned}
&dp_0[l+1][r][i+(t_0 \leq t_{n-l})] \\
&t_0
\end{aligned}\right.
$$
$$
dp_1[l][r+1][i+(t_1 \leq t_{r+1})] = \min\left\{\begin{aligned}
&dp_1[l][r+1][i+(t_1 \leq t_{r+1})] \\
&t_1
\end{aligned}\right.
$$
当 $dp_1 \neq \text{INF}$ 时，对于 $dp_1$ ，则有：
$$tNow = dp_1[l][r][i]$$
$$t_0 = tNow+m-(a_{n-l}-a_{r})$$
$$t_1 = tNow+a_{r+1}-a_{r}$$
转移方程与 $dp_0$ 同理。
初始化的时候把所有 $dp$ 置为无穷大，并把 $a_{n+1}$ 置为 $m$ （为了求得从原点到逆时针方向第一个邮票展台的距离），最后统计答案的时候求出：
$$
ans = \max_i
$$
其中： 存在 $l,r$ 使得 $dp_0[l][r][i]\neq \text{INF}$ 或 $dp_1[l][r][i]\neq \text{INF}$ 。
上代码：
```C++
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using std::min;
using std::max;
inline int& min_to(int& a,int b){
return a=min(a,b);
}
const int MAXN = 205;
int t[MAXN];
int a[MAXN];
int dp[MAXN][MAXN][MAXN][2];
signed main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",a+i);
for(int i=1;i<=n;i++)scanf("%d",t+i);
memset(dp,0x3f,sizeof(dp));
dp[0][0][0][0]=dp[0][0][0][1]=0;
a[n+1]=m;
for(int c=0;c<n;c++){
for(int l=0;l<=n;l++){
int r=c-l;
for(int i=0;i<=n;i++){
if(dp[l][r][i][0]!=0x3f3f3f3f){
int tNow = dp[l][r][i][0];
int time0 = tNow+a[n-l+1]-a[n-l];
int time1 = tNow+m-(a[n-l+1]-a[r+1]);
bool canGet0 = time0 <= t[n-l];
bool canGet1 = time1 <= t[r+1];
min_to(dp[l+1][r][i+canGet0][0],time0);
min_to(dp[l][r+1][i+canGet1][1],time1);
}
if(dp[l][r][i][1]!=0x3f3f3f3f){
int tNow = dp[l][r][i][1];
int time1 = tNow+a[r+1]-a[r];
int time0 = tNow+m-(a[n-l]-a[r]);
bool canGet0 = time0 <= t[n-l];
bool canGet1 = time1 <= t[r+1];
min_to(dp[l+1][r][i+canGet0][0],time0);
min_to(dp[l][r+1][i+canGet1][1],time1);
}
}
}
}
int ans = 0;
for(int l=0;l<=n;l++)for(int r=0;r<=n;r++)for(int i=0;i<=n;i++){
if(dp[l][r][i][0]!=0x3f3f3f3f || dp[l][r][i][1]!=0x3f3f3f3f)
ans=max(ans,i);
}
printf("%d\n",ans);
return 0;
}
```
~~（P.S. 刚把程序写出来的时候区间左端点的变量名`l`和周长`l`重名了，调了半节课才发现，遂把周长改成了`m`~~
这道题给了我们一个新的思路，就是如果某个状态不好表示，可以把状态变成值，所求变为下标，最后扫描一遍$dp$统计答案。