题解：P14300 [JOI2023 预选赛 R2] 货物列车 / Freight Train

· · 题解

给一个 O(n^3\log n) 的写法。

前言

为了方便，把 2\sim n 的物品下标换到 1\sim {n-1}，且将 n 减 1，d 除以 2，这样可以将距离从 2*(i-1) 变为 i，显然对答案无影响。

思路

考虑朴素 dp，设计 f_{i,j} 表示考虑前 i 个数，用了 j 的路程的最大价值，那其实就是一个空间为 d 的背包，每个物品体积为 i，价值是转移区间里前 w 大的数，记 ans_{l,r} 表示区间 l\sim r 中前 w 大的数，转移显然：

f_{i,j}=\max_{k=0}^{k<i}f_{k,j-i}+ans_{k+1,i}

暴力转移复杂度 O(n^4)，考虑优化。

容易发现 ans_{l,r} 是满足四边形不等式的，证明显然，那么直接决策单调性，分治优化 dp 即可。不会的看 这里。

复杂度 O(n^3\log n)，注意要特判 w=1 的情况。

代码

注意不要开 long long，空间会炸。

#include<bits/stdc++.h>
using namespace std;
const int N=460;
int n,w,d;
int f[N][N*N],ans[N][N],a[N];
int tmp[N];
int query(int l,int r){
    int ans=0,c=0;
    for(int i=l;i<=r;i++) tmp[++c]=a[i],ans+=a[i];
    if(c<=w) return ans;
    sort(tmp+1,tmp+c+1);
    ans=0;
    for(int i=c;i>=c-w+1;i--) ans+=tmp[i];
    return ans;
}
void solve(int i,int l,int r,int L,int R){
    if(l>r) return;
    int mid=l+r>>1,mx=0,k=0;
    for(int j=L;j<=R;j++)
        if(f[j][mid-i]+ans[j+1][i]>mx){
            mx=f[j][mid-i]+ans[j+1][i];
            k=j;
        }
    f[i][mid]=mx;
    solve(i,l,mid-1,L,k);
    solve(i,mid+1,r,k,R);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>w>>d;
    --n,d/=2;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(w==1){
        int ans=0;
        for(int i=1;i<=n;i++)
            for(int j=0;j<=d;j++)
                if(j>=i) f[i][j]=max(f[i-1][j],f[i-1][j-i]+a[i]),ans=max(ans,f[i][j]);
                else f[i][j]=f[i-1][j];
        return cout<<ans,0;
    }
    for(int l=1;l<=n;l++)
        for(int r=l;r<=n;r++)
            ans[l][r]=query(l,r);
    for(int i=1;i<=n;i++) solve(i,i,d,0,i-1);
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=i;j<=d;j++)
            ans=max(ans,f[i][j]);
    cout<<ans;
    return 0;
}