题解：P17679 [IO 2025 #4] 黑客任务

wsy_I · 2026-10-23 20:24:11 · 题解

DP 板刷计划第三题。官评蓝，自评绿青之间。

这个题，比较简单的矩阵优化 DP 吧。不知道为啥蓝，我一眼秒的 DP 青顶天了。本文定义 z=26，即键盘非空格字符个数。

首先考虑暴力 DP 怎么做。设 dp_{i,p} 表示已经输入 i 个单词，最后的手位置停留在 p 的手指移动次数。其中 p 是一个代表位置的二元组。

我们定义 \operatorname{dis}(p_1,p_2) 表示这两个二元组的距离，那么有转移：枚举每一个结尾在这个位置的单词，考虑每一个位置到其开头位置的距离，然后取 \min 即可。

形式化的，定义 \operatorname{end}(s) 表示字符串 s 的末尾位置，\operatorname{start}(s) 表示字符串 s 的开头位置，\operatorname{cost}(s) 表示字符串 s 内部移动代价，则：

那么现在我们得到了一个 O(knz) 的 DP。我们注意到同一个 \operatorname{end} 的时候只有 \operatorname{cost} 是最小的字符串是有用的，可以优化到 O(kz^2)，但是还是不足以通过。

接着上矩阵加速。构造转移矩阵 mt，表示 mt_{1,p}\to mt_{p,1} 的转移系数。那么 mt^k 的最小值即为答案（矩阵乘法是 (\min,+) 矩阵乘法）。

然后考虑怎么推出这个转移矩阵。其实比较简单，令 mt 初始为全 +\infin，每一次遇到一个字符串的时候，枚举上一个的结尾位置，使用类似上面的 DP 式子的方法对于 mt 取 \min 即可。

所以复杂度优化为 O(|s|+nz+z^3\log k)，可以通过。

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++ ) 
#define per(i, l, r) for(int i = (l); i >= (r); i -- )
#define frein(s) freopen(s, "r", stdin)
#define freout(s) freopen(s, "w", stdout)
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e5 + 5;
const int S = 26 + 5;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n, k, p[3][9], cnt, ans = INF;
pair<int, int> pos[S]; 
string s[N], kyb[3];
int dis(pair<int, int> x, pair<int, int> y)
    { return abs(x.first - y.first) + abs(x.second - y.second); }

struct Matrix {
    int m[S][S];
    Matrix() { memset(m, 0x3f, sizeof m); }
    auto operator [] (int x) { return m[x]; }
} mt;

Matrix operator * (Matrix a, Matrix b) {
    Matrix c;
    rep(i, 1, 26) rep(k, 1, 26)
        rep(j, 1, 26) c[i][j] = min(a[i][k] + b[k][j], c[i][j]);
    return c;
}

Matrix qpow(Matrix a, int b) {
    Matrix res;
    rep(i, 1, 26) res[i][i] = 0;
    for(; b; a = a * a, b >>= 1) if(b & 1) res = res * a;
    return res;
}

signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k;
    rep(i, 1, n) cin >> s[i];
    cin.ignore();
    rep(i, 0, 2) getline(cin, kyb[i]);
    rep(i, 0, 2) rep(j, 0, 8) {
        if(kyb[i][j] != ' ') {
            pos[kyb[i][j] - 'a'] = make_pair(i, j);
            p[i][j] = ++ cnt;
        }
    } 
    rep(i, 1, n) {
        int res = 0;
        rep(j, 0, (int)s[i].size() - 2) res += dis(pos[s[i][j] - 'a'], pos[s[i][j + 1] - 'a']);
        rep(j, 0, 2) rep(k, 0, 8) {
            int p1 = p[j][k];
            pair<int, int> ps = pos[s[i].back() - 'a'];
            int p2 = p[ps.first][ps.second];
            mt[p1][p2] = min(mt[p1][p2], dis(make_pair(j, k), pos[s[i].front() - 'a']) + res);
        }
    }
    mt = qpow(mt, k);
    rep(i, 1, 26) rep(j, 1, 26) ans = min(ans, mt[i][j]);
    cout << ans << endl;
    return 0;
}