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

· · 题解

经过一个打卡点有四种方式：

考虑在东向电车行走的路线，可以跳过若干打卡点不走，其余走 u+v，或者走 u+e 上去，把没走的打卡点挑若干个走 e+d，挑一个走 d+v 下去。

注意 u+e 和 d+v 可能被走多次。

将 e+d 和 d+v 的贡献后置，在转移时加上额外贡献，令 f_{i,j,k} 表示到了站台 i，有 j 个打卡点被指定走 d+e，k 个打卡点被指定走 d+v，转移时加上 2T(j+k) 的贡献，枚举当前有 k_1 个 u+e 和前面匹配，k_2 个 d+v 和后面匹配。可以做到 O(\text{poly}(n))。

简化状态，由于在上面只能往左走，因此只有存在没有匹配的 d+v 时才能匹配存在未匹配的 d+e，另一方面，我们做 u+e 和 d+v 的匹配时实际上顺便把 d+e 走了，可以把向上和向下理解称括号匹配，当存在未匹配的左括号时可以选择 d+e。

令 dp_{i,j} 表示到了站台 i，有 j 个未匹配的 d+v 的最小代价。

转移时，可以选择 u+v，当 j>0 时可以选择 d+e。枚举这个站台有 k1 个 u+e 和前面匹配，k2 个 d+v 和后面匹配，转移到 dp_{i+1,j-k1} 或 dp_{i+1,j+k2}。

前缀和优化可以做到 O(n^2)。

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