自动搬运

查看原文

来自洛谷，原作者为

	虚空之灵 **

搬运于2025-08-24 22:24:52，当前版本为作者最后更新于2020-11-20 16:09:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

个人博客链接

题目

题目（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]$$

$l$ 表示原点逆时针方向取到的邮票个数， $r$ 表示原点顺时针方向取到的邮票个数， $k$ 表示当前已经取得的邮票数量， $dp$ 的值表示取得这些邮票所需要的最小时间， $dp_0$ 和 $dp_1$ 分别表示当前位于区间左端点和区间右端点的情况。

设周长为 $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}$ 。

上代码：

#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$统计答案。