P6649 「SWTR-05」Grid

Wf_yjqd · 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;
}