题解：P14424 [JOISC 2014] 邮戳收集 / Collecting Stamps

· · 题解

很帅的题。直接对着列车的移动路径刻画还是太困难了，因为列车可以重复经过一些位置。考虑刻画经过邮戳台的路径的方案，发现总共有四种走法：从上行列车走上去再走下去 u_i+v_i、从下行列车走下去再走上来 d_i+e_i、从上行列车走上去再走上去到下行列车 u_i+e_i、从下行列车走下去再走下去到上行列车 d_i+v_i。下文按顺序称呼这四种走法为第一、二、三、四种走法。

注意到如果我们用第三种走法走了上去，那么移动路径会形如：从下行列车往回走几站之后，在前面的一个站选择第四种走法下去，并用上行列车坐回来。如果我们用一对括号去刻画的话，其实就是若这里有一个右括号，则左边必然要存在一个左括号与之匹配！于是我们称第四种走法为左括号、第三种走法为右括号，那么一组合法的邮戳台行走方案其实就是一个合法的括号串中间穿插着一些空的位置（这些位置我们用第一、二种走法即可）。

而括号串是好 dp 的，常见的套路就是记一下前缀还有多少个未匹配的左括号，对于本题我们也是这么干的。令 f_{i,j} 代表，考虑到了前 i 个车站中所有邮戳台的走法，其中还有 j 个未匹配的左括号的最小代价。转移是容易的，枚举当前选择哪种走法，考虑完全背包的同层转移即可，这里不再赘述，可以参考代码理解。

说一下如何处理列车走一站的代价 T，考虑费用前置的 Trick，首先上行列车至少有要坐 n+1 次列车到终点的贡献，即 (n+1)T，这部分我们提前加到答案里；考虑什么时候我们会额外多走一些站，当我们用右括号走上去并「往回走、下去、走回来」的时候，会额外造成 2kT 的代价，其中 k 是左右括号间的距离。那么直接对这个费用前置即可，对于每个 f_{i,j}，将其代价额外增加 2Tj 即可，代表上、下行列车中，i 这段会额外增加 2Tj 的贡献，因为这 j 个左括号会在未来 i 的后面被匹配，每匹配一次 i 这段就会被列车额外经过 2 次。

复杂度 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,T;
int u[N],v[N],d[N],e[N];
long long f[N][N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>T;
    for(int i=1;i<=n;i++){
        cin>>u[i]>>v[i]>>d[i]>>e[i];
    }
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=min(f[i][j],f[i-1][j-1]+d[i]+v[i]); //"("
        }
        for(int j=0;j<n;j++){
            f[i][j]=min(f[i][j],f[i-1][j+1]+e[i]+u[i]); //")"
        }
        for(int j=0;j<=n;j++){
            f[i][j]=min(f[i][j],f[i-1][j]+u[i]+v[i]);
        }
        for(int j=1;j<=n;j++){
            f[i][j]=min(f[i][j],f[i-1][j]+d[i]+e[i]);
        }
        for(int j=1;j<=n;j++){
            f[i][j]=min(f[i][j],f[i][j-1]+d[i]+v[i]);
        }
        for(int j=n-1;j>=0;j--){
            f[i][j]=min(f[i][j],f[i][j+1]+e[i]+u[i]);
        }
        for(int j=0;j<=n;j++){
            f[i][j]+=2*j*T;
        }
    }
    cout<<f[n][0]+1ll*(n+1)*T;
    return 0;
}