题解：AT_joi2020ho_c スタンプラリー 3 (Collecting Stamps 3)

· · 题解

前言

一道 DP 大运，可能我的转移有些复杂，大家了解一下状态，转移最好还是自己写吧（或许有更简单的转移）。被大运撞飞。

思考

假设主人公已经经过了一段区间的点，那他肯定最终会停留在这个区间的两端（如果不是在两端那说明他到了两端之后又往回走了，这不优）。

状态定义

一个四位状态，d_{i,j,k,0/1} 表示主人公已经经过了 1\sim i,j\sim n 号点，集到了 k 张邮票，此时停留在 i 还是 j 的最少耗时。

转移

由 i-1,j 和 i,j+1 转移而来，判断一下新到的点能不能集到邮票，之后就是大力转移。还是看代码吧。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=205;
long long n,m,a[maxn],b[maxn],d[maxn][maxn][maxn][2],ans;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    memset(d,0x3f,sizeof(d));
    d[1][n+1][0][0]=a[1];
    d[1][n+1][0][1]=a[1]*2;
    if(a[1]<=b[1])
    {
        d[1][n+1][1][0]=a[1];
        d[1][n+1][1][1]=a[1]*2;
    }
    d[0][n][0][1]=m-a[n];
    d[0][n][0][0]=(m-a[n])*2;
    if(m-a[n]<=b[n])
    {
        d[0][n][1][1]=m-a[n];
        d[0][n][1][0]=(m-a[n])*2;
    }
    a[n+1]=m;
    for(long long i=0;i<=n;i++)
    for(long long j=n+1;j>i;j--)
    for(long long k=0;k<=n;k++)
    {
        long long s=a[i]+m-a[j];
        if(i>0)d[i][j][k][0]=min(d[i][j][k][0],min(d[i-1][j][k][0]+a[i]-a[i-1],d[i-1][j][k][1]+s));
        if(j<=n)d[i][j][k][0]=min(d[i][j][k][0],min(d[i][j+1][k][0]+s,d[i][j+1][k][1]+a[j+1]-a[j])+s);
        if(i>0&&d[i-1][j][k-1][0]+a[i]-a[i-1]<=b[i])d[i][j][k][0]=min(d[i][j][k][0],d[i-1][j][k-1][0]+a[i]-a[i-1]);
        if(i>0&&d[i-1][j][k-1][1]+s<=b[i])d[i][j][k][0]=min(d[i][j][k][0],d[i-1][j][k-1][1]+s);
        if(j<=n&&d[i][j+1][k-1][0]+s<=b[j])d[i][j][k][0]=min(d[i][j][k][0],d[i][j+1][k-1][0]+s*2);
        if(j<=n&&d[i][j+1][k-1][1]+a[j+1]-a[j]<=b[j])d[i][j][k][0]=min(d[i][j][k][0],d[i][j+1][k-1][1]+a[j+1]-a[j]+s);
        if(i>0)d[i][j][k][1]=min(d[i][j][k][1],min(d[i-1][j][k][0]+a[i]-a[i-1],d[i-1][j][k][1]+s)+s);
        if(j<=n)d[i][j][k][1]=min(d[i][j][k][1],min(d[i][j+1][k][0]+s,d[i][j+1][k][1]+a[j+1]-a[j]));
        if(i>0&&d[i-1][j][k-1][0]+a[i]-a[i-1]<=b[i])d[i][j][k][1]=min(d[i][j][k][1],d[i-1][j][k-1][0]+a[i]-a[i-1]+s);
        if(i>0&&d[i-1][j][k-1][1]+s<=b[i])d[i][j][k][1]=min(d[i][j][k][1],d[i-1][j][k-1][1]+s*2);
        if(j<=n&&d[i][j+1][k-1][0]+s<=b[j])d[i][j][k][1]=min(d[i][j][k][1],d[i][j+1][k-1][0]+s);
        if(j<=n&&d[i][j+1][k-1][1]+a[j+1]-a[j]<=b[j])d[i][j][k][1]=min(d[i][j][k][1],d[i][j+1][k-1][1]+a[j+1]-a[j]);
        if(d[i][j][k][0]<d[0][0][0][0]||d[i][j][k][1]<d[0][0][0][0])ans=max(ans,k);
    }
    cout<<ans;
}
/*
!(^w^)?
*/

好运。