题解：CF2049D Shift + Esc

· · 题解

分析

我们可以注意到每一行的调整是独立的，且调整次数的贡献是线性可拆的，考虑 \texttt{DP}。

因此令 dp_{i,j,k} 为当前到达点 (x,y)，并且第 i 行向左移动了 k 位，k \in [0,m-1]。

每次 dp_{i,j,k} 仅可以从上一行 dp_{i-1,j,l} 转移过来，l \in [0,m-1] 以及从 dp_{i,j-1,k} 转移过来。

于是就得到一下转移方程：

dp_{i,j,k}=min(dp_{i-1,j,l}+k \times K,dp_{i,j-1,k})+a_{i,(j+k-1) \bmod m+1}

其中 K 为题目中描述的 k。

可是我们要循环枚举 i，j，k，l，时间复杂度为 O(nm^3)，超时了，还要优化。

我们发现，在 l 这一维度是可以优化掉的。

由于一定要使 dp_{i-1,j,l} 最小，可以在之前循环枚举到 (i-1,j) 时记录最小的 dp_{i-1,j,k} 即可。

我们将最小的 dp_{i,j,k} 记为 f_{i,j}：

f_{i,j}=min(dp_{i,j,k}),k \in [0,m-1]

那么转移方程变为：

dp_{i,j,k}=min(f_{i-1,j}+k \times K,dp_{i,j-1,k})+a_{i,(j+k-1) \bmod m+1}

时间复杂度 O(nm^2)，可以通过。

Code

码风不正，请多多谅解。

#include<bits/stdc++.h>
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar/*_unlocked*/();
    while (ch<48||ch>57) {
        if (ch=='-') f=-1;
        ch=getchar/*_unlocked*/();
    }
    while (ch>=48&&ch<=57) {
        x=x*10+ch-48;
        ch=getchar/*_unlocked*/();
    }
    return x*f;
}

template<typename T>
inline void write(T x,int f=1) {
    if(x<0) putchar/*_unlocked*/('-'),x=-x;
    if(x>9) write(x/10,0);
    putchar/*_unlocked*/(x%10+'0');
    if(f==1)putchar/*_unlocked*/('\n');
    if(f==2) putchar/*_unlocked*/(' ');
    return;
}
long long dp[310][310][310],f[310][310];
int a[310][310];

int main(){
    int t=read();
    while(t--){
        int n=read(),m=read(),k1=read();
        for(register int i = 1;i <= n;i++) for(register int j = 1;j <= m;j++) for(register int k = 0;k < m;k++) dp[i][j][k]=LONG_LONG_MAX;
        for(register int i = 1;i <= n;i++) for(register int j = 1;j <= m;j++) a[i][j]=read(),f[i][j]=LONG_LONG_MAX;
        for(register int i = 1;i <= n;i++) for(register int j = 1;j <= m;j++){
            if(i!=1||i==1&&j==1)for(register int l = 0;l < m;l++){
                dp[i][j][l]=min(dp[i][j][l],f[i-1][j]+a[i][(j+l-1)%m+1]+1ll*l*k1),f[i][j]=min(f[i][j],dp[i][j][l]);
            }
            if(j!=1)for(register int k = 0;k < m;k++){
                dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k]+a[i][(j+k-1)%m+1]),f[i][j]=min(f[i][j],dp[i][j][k]);
            } 
        }
        long long minn=1e18;
        for(register int i = 0;i < m;i++) minn=min(minn,dp[n][m][i]);
        write(minn);
    }
    return 0;
}

完结撒花。