【CF】Day24——Codeforces Round 994 (Div. 2) D

D. Shift + Esc

题目：

思路：

典DP的变种

如果这一题没有这个变换操作，那么是一个很典型的二维dp，每一个格子我们都选择上面和左边中的最小值即可

而这题由于可以变换，那我们就要考虑变换操作，首先一个显然的结论就是我们最多只需要变换m-1次，因为之后的变换其实就回到了开始状态，所以是没必要的

这里我们就可以使用一个 dp[i][j][k] ，其定义为 (i,j) 位置在变换 k 次后的最小值

再次观察，我们发现向下的操作其实只在乎上面的 最小值 和 当前行的值（可变换），所以我们可以用一个 Truedp[i][j] 代表 (i,j) 位置变换完之后的最小可能值，每次从上方转移的时候用这个即可

代码注意变换操作的细节即可

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <memory>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"

int n, m, k;

int get(const vector<vector<int>>& a,int i, int j, int add)
{
    int tmp = (j + add) % m;
    return tmp == 0 ? a[i][m] : a[i][tmp];
}

void solve()
{
    cin >> n >> m >> k;
    vector<vector<int>> mp(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> mp[i][j];
        }
    }
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(m+1,1e18)));
    vector<vector<int>> Truedp(n + 1, vector<int>(m + 1, 1e18));
    Truedp[0][1] = Truedp[1][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int x = 0; x < m; x++)
            {
                dp[i][j][x] = min(dp[i][j][x], Truedp[i - 1][j] + get(mp,i,j,x) + 1LL*x*k);
                dp[i][j][x] = min(dp[i][j][x], dp[i][j-1][x] + get(mp, i, j, x));
                Truedp[i][j] = min(Truedp[i][j], dp[i][j][x]);
            }
        }
    }
    cout << Truedp[n][m] << endl;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}