https://codeforces.com/contest/2049/problem/D
一眼dp。猜测状态表示为$f[i][j]：移动到i行j列所需要的最小代价$
难点在怎么进行状态转移。苯人思维走偏了，一直想求出，在i行，从j列到k列的最小代价来帮助转移，但是这个时间复杂度不可承受。
不妨回到最原始的表达，不带shift的话，状态转移方程为：
$$f[i][j]=min(f[i-1][j],f[i][j-1]) + a[i][j]$$
带shift的话，我们加一维状态不就好了？求$g[i][j][x]:移动到i行j列，第i行shift了x次的最小代价$
考虑状态转移，从上一行转移下来的话（方便起见行坐标从1到n，列坐标从0到m），是到达i-1行j列的最小代价，加上i行j列在shift了x次的情况下的$a[i][j]$：
$$min\{g[i-1][j][x]\} + a[(j+x)\%m] + shift代价\\ = f[i-1][j] + a[(j+x)\%m] + k*x$$
从这一行左边一格转移过来的话：
$$g[i][j-1][x] + a[i][(j+x)\%m]$$
综上，状态转移方程为：
$$ g[i][j][x] = min(f[i-1][j]+a[i][(j+x)\%m] + k*x,g[i][j-1][x] + a[(j+x)\%m])\\ f[i][j] = min(g[i][j][x],)x\in [0,m) $$
注意到从$g[i][j-1][x]$转移来的话必须要j大于0，修改成取模形式的话可以写在一个式子里：

for(int j=0;j<m;j++) 
    tmp[j] = min(tmp[(j-1+m)%m] + a[i][(j+shift)%m],dp[i-1][j] + a[i][(j+shift)%m] + 1ll*shift*k);

完整代码：

void solve(){
    ll n,m,k;
    cin>>n>>m>>k;
    vector<vector<ll>> dp(n+1,vector<ll>(m+1,1e18));
    vector<vector<ll>> a(n+1,vector<ll>(m));
    for(int i=1;i<=n;i++)
        for(int j=0;j<m;j++)
            cin>>a[i][j];

    dp[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int shift = 0;shift < m;shift++){
            vector<ll> tmp(m+1,1e18);
            for(int j=0;j<m;j++) tmp[j] = min(tmp[(j-1+m)%m] + a[i][(j+shift)%m],dp[i-1][j] + a[i][(j+shift)%m] + 1ll*shift*k);
            //for(int j=1;j<m;j++) tmp[j] = min(tmp[j],tmp[(j-1+m)%m] + a[i][(j+shift)%m]);
            for(int j=0;j<m;j++) dp[i][j]  = min(dp[i][j],tmp[j]);
        }
    }
    cout<<dp[n][m-1]<<endl;

}