自动搬运

查看原文

来自洛谷，原作者为

	Wf_yjqd 哀酱永远的神/tyt /se /qq!!!

搬运于2025-08-24 22:22:46，当前版本为作者最后更新于2023-05-05 00:15:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

额么么，某年某市某区区赛搬运了这道题。

时隔一年，回来补题。

一眼动态规划。

考虑设 $f_{i,j}$ 表示从第 $i$ 行，第 $j$ 列进入下一行时的最小代价。

那么如何转移呢？

显然，进入第 $i$ 行时的列数一定是 $\ge j$ 的，这样才能到达第 $j$ 列。

考虑从刚进到第 $i$ 行的点 $k$ 跑到 $j$ 的路径上的点一定是要算代价的，而同时可以再往左跑一段后跑回来。

后者可以预处理一个以 $j$ 为终点的最小子段和，但前者难道要枚举 $k$ 吗？

显然不行，这样此题复杂度就成 $\operatorname{O}(n^3)$ 的了（虽然某区赛可以过）。

我们可以想到再维护一个以 $j$ 为起点的最小子段和，不过我们还需要处理上一行进到 $k$ 时的最小代价和，这个只用把长度为 $1$ 的子段代价加上 $f_{i-1,j}$ 即可。

于是此题复杂度 $\operatorname{O}(n^2)$。

空间上可以滚动数组，不过没必要，总体量级也没变，注释里有。

寄 long long 的代码、、

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e3+84;
ll n,m,ans=0x7f7f7f7f,val[maxn][maxn],f[maxn][maxn],hzn[maxn],qzn[maxn];
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=n;i>=1;i--)
        for(ll j=1;j<=m;j++)
            scanf("%lld",&val[i][j]);
    for(ll i=1;i<=n;i++){
        memset(hzn,0x7f,sizeof(hzn));
        memset(qzn,0x7f,sizeof(qzn));
        for(ll j=1;j<=m;j++)
            qzn[j]=min(qzn[j-1],0ll)+val[i][j];
        for(ll j=m;j>=1;j--)
            hzn[j]=min(hzn[j+1],f[i-1][j])+val[i][j];
            // hzn[j]=min(hzn[j+1],f[j])+val[i][j];滚动数组
        for(ll j=1;j<=m;j++)
            f[i][j]=min(hzn[j]+qzn[j]-val[i][j],hzn[j]);
            // f[j]=min(hzn[j]+qzn[j]-val[i][j],hzn[j]);滚动数组
        //     printf("%lld %lld %lld %lld %lld Sherry\n",i,j,hzn[j],qzn[j],val[i][j]);
        // }
    }
    for(ll i=1;i<=m;i++)
        ans=min(ans,f[n][i]);
    printf("%lld",ans);
    return 0;
}