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

容易发现，除了移动距离最近的那一次，剩下的每一次都会把 \(w\) 个货物运会 \(1\) 号点。
考虑 \(dp\) 设 \(f_{i,j,k}\) 表示在后 \(i\) 个中运货物，目前装了 \(j\) 个，移动了 \(k\) 步的最大价值。
转移 \(f_{i,j,k}=\left\{\begin{matrix}\max(f_{i+1,j,k},f_{i+1,j-1,k}+a_i)\ \ \ \ \ \ \ \ \ \ \ \ j>1\\\max(f_{i+1,j,k},f_{i+1,w,k-2*(i-1)}+a_i)\ \ \ j=1\end{matrix}\right.\)。
第一维可以用滚动数组优化掉，空间复杂度变成 \(\mathcal O(n^3)\)，但时间复杂度依然为 \(\mathcal O(n^4)\)。
有一个非常牛的方法：当步数足够把所有的货物运回 \(1\) 时直接输出，否则步数上限就是 \(\frac{n^2}w\) 级别的，第 \(2\) 维乘第 \(3\) 维是 \(n^2\),总时间复杂度 \(\mathcal O(n^3)\)，可以直接通过，不卡常。

代码

/*
Luogu P14300 [JOI2023 预选赛 R2] 货物列车 / Freight Train
2026-03-20
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=460;
int n,w,d,a[maxn],f[2][maxn][maxn*maxn],cs;
signed main(){
    read(n,w,d);
    for(int i=2;i<=n;i++) read(a[i]);
    for(int i=n;i>=1;i-=w) cs+=2*(i-1);
    if(cs<=d){
        int h=0;
        for(int i=2;i<=n;i++) h+=a[i];
        write(h);
        return 0;
    }
    memset(f,-0x3f,sizeof(f));
    f[n+1&1][w][0]=0;
    for(int i=n;i>=1;i--) for(int j=1;j<=w;j++) for(int k=0;k<=d;k++){
        if(j!=1) f[i&1][j][k]=max(f[i+1&1][j][k],f[i+1&1][j-1][k]+a[i]);
        else{
            if(k>=(i-1)*2) f[i&1][j][k]=max(f[i+1&1][j][k],f[i+1&1][w][k-(i-1)*2]+a[i]);
            else f[i&1][j][k]=f[i+1&1][j][k];
        }
    }
    int ans=0;
    for(int i=1;i<=w;i++) for(int j=1;j<=d;j++) ans=max(ans,f[1][i][j]);
    write(ans);
    return 0;
}