目录

棋盘类 DP （允许改 ≤k≤k 个字母后字典序最小路径构造类型）

题目描述

给一个 n×nn\times n 的小写字母矩阵，你最多可以把 不超过 kk 个格子的字母改成任意字母。只能从 (1,1)(1,1) 走到 (n,n)(n,n) ，每步向右或向下；路径经过的字母按顺序拼成长度 2n−12n-1 的字符串。

问：在最多改 kk 个格子的前提下，能得到的 字典序最小 路径字符串是什么。

输入输出样例

输入 #1

4 2
abcd
bcde
bcad
bcde

输出 #1

aaabcde

输入 #2

5 3
bwwwz
hrhdh
sepsp
sqfaf
ajbvw

输出 #2

aaaepfafw

输入 #3

7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz

输出 #3

aaaaaaadudsnz

解题思路

该题目相比于 浅谈棋盘类DP（二） 中的问题多了一个修改的部分，就需要关注这部分。

首先要求最终的结果 字典序最小 ，正常走的时候可能会生成一个 字典序 AA ，然后通过修改之后得到一个 字典序 BB ，在本问题中这两个字典序的长度还是相同的。

字典序最小 可以理解成 像查字典一样比较两个字符串谁更靠前 。
给两个字符串 AA 和 BB（长度可以相同也可以不同），比较规则是：

  1. 从左到右找到 第一个不同的位置 tt 。
  2. 如果 At<BtA_t < B_t（按字符的大小，比如 'a'<'b'<'c'），那么 AA 的字典序更小；反之 BB 更小。
  3. 如果一直到某个字符串结束都没找到不同字符：
    • 那么 更短的那个更小 。例如 "abc" < "abcd"。

例子

  • "abz" 和 "aca"：第 22 位不同，'b'<'c'，所以 "abz" < "aca"（后面不用看了）。
  • "aaa" 和 "aab"：第 33 位不同，'a'<'b'，所以 "aaa" < "aab"。
  • "abc" 和 "abc"：完全一样，不分大小。
  • "abc" 和 "abca"：前 33 位相同，短的 "abc" 更小。

根据上面的部分很明显可以观察到如果想要让得到的 字典序最小 ，就需要把前面的部分修改了，把这个字典序 从左到右 尽量把字符改成 'a' ，这是解决该问题的 关键小结论 。

因为：

  • 'a' 是最小字母；
  • 字典序只看最早不同位，所以 如果某一位能改成 'a'，永远不亏 ；
  • 因此在一条给定路径上，用预算把最早的非 'a' 尽量改成 'a'，得到该路径的最小字符串。

由此可得到 暴力解法

  1. DFS / 回溯枚举所有由 R / D 组成的路径（共 (2n−2n−1)\binom{2n-2}{n-1} 条）。
  2. 对每条路径记录经过格子的字符序列 tt ，把前面最多 kk 个非 'a' 改成 'a' 得到 tmint_{min} 。
  3. 全局取最小 tmint_{min} 。

路径数是 (2n−2n−1)\binom{2n-2}{n-1}，每条路径处理 O(2n)O(2n)。

O((2n−2n−1)⋅n)O\left(\binom{2n-2}{n-1}\cdot n\right)

只能用于很小的 nn（比如 n≤12n\le 12 左右）。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, k;
char s[N][N];
string Ans;
// 固定一条路径字符串 t：用最多 k 次把最早的非 'a' 改成 'a'
string f(string t) {
    int rem = k;
    for (char &c : t) {
        if (rem > 0 && c != 'a') {
            c = 'a';
            rem--;
        }
    }
    return t;
}
void dfs(int x, int y, string t) {
    // t 已经包含 (x, y) 的字符
    if (x == n && y == n) {
        string Res = f(t);
        if (Ans.empty() || Res < Ans) Ans = Res;
        return;
    }
    if (y + 1 <= n) dfs(x, y + 1, t + s[x][y + 1]); // 右 (x, y + 1)
    if (x + 1 <= n) dfs(x + 1, y, t + s[x + 1][y]); // 下 (x + 1, y)
}
inline void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    dfs(1, 1, string(1, s[1][1]));
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

既然都已经写暴力 DFS 了，不妨加一个剪枝做个小优化，虽然并没有什么 🥚 用，可以解决 n≤14n \le 14 左右的数据。

加上：

  1. 在线生成改 kk 次后的输出字符串前缀（不用等到叶子再贪）
  2. 字典序剪枝：一旦当前前缀已经比 AnsAns 的对应前缀更大，就直接砍掉这棵子树
    同时再加一个小优化：优先走下一位输出字符更小的分支 ，更快得到一个很小的 AnsAns ，从而剪枝更猛（猛个 🥚）。
正确性

对任意路径，最优改法 就是把 整条路径上最早出现的 kk 个非 'a' 改成 'a' 。
因此当走到某个前缀时，这个前缀在最终输出串里 已经确定 （以后不会被 未来的修改 影响），所以可以拿来和当前 AnsAns 做字典序比较剪枝。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 2e3 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, k;
char s[N][N];
string Ans;
char buf[2 * N];    // 当前改 k 次后的输出串前缀（在线构造）
// (x, y) 当前坐标（1 - index）
// rem   还剩多少次把非 'a' 改成 'a' 的机会（只会用于最早出现的非 'a'）
// cmp   当前前缀与 Ans 的比较状态：0 = 完全相等，-1 = 已小于，1 = 已大于（1 会被剪掉，不会递归进去）
// len   buf 当前长度 
void dfs(int x, int y, int rem, int cmp, int len) {
    if (x == n && y == n) {
        string Res(buf, buf + len);
        if (Ans.empty() || Res < Ans) Ans = Res;
        return;
    }
    struct Opt {
        int nx, ny, nrem;
        char outc;
    };
    Opt opts[2];
    int cnt = 0;
    auto add_opt = [&](int nx, int ny) {
        char c = s[nx][ny];
        Opt o;
        o.nx = nx; o.ny = ny;
        if (c != 'a' && rem > 0) {
            o.outc = 'a';
            o.nrem = rem - 1;
        } else {
            o.outc = c;
            o.nrem = rem;
        }
        opts[cnt++] = o;
    };
    if (y + 1 <= n) add_opt(x, y + 1); // 右
    if (x + 1 <= n) add_opt(x + 1, y); // 下
    // 优先扩展下一位输出字符更小的分支，尽快拿到更小 Ans
    if (cnt == 2 && (opts[1].outc < opts[0].outc)) swap(opts[0], opts[1]);
    for (int i = 0; i < cnt; i++) {
        auto o = opts[i];
        // 字典序剪枝：比较新加入这一位与 Ans 对应位
        int ncmp = cmp;
        if (!Ans.empty() && cmp == 0) {
            char bc = Ans[len]; // 新字符将放在 buf[len]
            if (o.outc > bc) continue;     // 前缀已经更大，直接剪掉
            if (o.outc < bc) ncmp = -1;    // 已经更小，后面无需再和 Ans 精确比对
        }
        buf[len] = o.outc;
        dfs(o.nx, o.ny, o.nrem, ncmp, len + 1);
    }
}
inline void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    // 起点也可能被改成 'a'
    int rem = k;
    char c = s[1][1];
    if (c != 'a' && rem > 0) {
        buf[0] = 'a';
        rem--; 
    }
    else buf[0] = c;
    // cmp 初始为 0（因为 Ans 还空，不影响）
    dfs(1, 1, rem, 0, 1);
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

可以观察到

DFS 是 按路径展开 ；
那么就可以用朴素 DP 把所有到同一个状态 (i,j,改了t)(i,j,\text{改了}t) 的路径合并 ，只保留其中字典序最小的那条字符串。

这样就不需要枚举 (2n−2n−1)\binom{2n-2}{n-1} 条路径了（依然很暴力，只是因为存字符串的原因暴力而已）。

定义

$$dp_{i,j,t} \text{在所有从 }(1,1)\text{ 到 }(i,j)\text{ 的路径上，选择恰好 }t\text{ 个经过的格子修改其字母后所得字符串中，字典序最小的那个} $$

注意：一旦决定 改 某个格子，最优一定改成 'a'（因为 'a' 最小，字典序最优永远不亏）。

初始化

起点两种可能：

  • 不改：dp1,1,0=string(1,s1,1)dp_{1, 1, 0} = string(1, s_{1, 1}) 。

  • 若 s1,1≠’a’s_{1, 1} \neq \text{'a'} 且 k≥1k\ge1：改成 ’a’\text{'a'} ， dp1,1,1=’a’dp_{1, 1, 1} = \text{'a'} 。

转移

到 (i,j)(i,j) 只能 从上 / 左 来：

  • 不改当前格：从 dpprev,tdp_{prev,t} 过来，末尾加 si,js_{i, j} 。

  • 改当前格为 'a' （只有当 si,j≠’a’s_{i, j} \neq \text{'a'} 且 t≥’a’t \ge \text{'a'} 才有意义）：从 dpprev,t−1dp_{prev, t-1} 过来，末尾加 'a'

每个 dpi,j,tdp_{i, j, t} 取字典序最小者。

最终输出 min⁡0≤t≤kdpn,n,t\min_{0\le t\le k} dp_{n, n, t}

时间复杂度

  • 状态数：n2(k+1)n^2(k+1)

  • 但每次更新会复制 / 比较长度 O(n)O(n) 的字符串
    ⇒ 总体大概 O(n3k)O(n^3k) 级，大数据必炸 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 50 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, k, ok[N][N][N * N];  // ok 标记该状态是否可达
char s[N][N];  
string dp[N][N][N * N]; // N = 50 + 10 ，太大会爆炸，因为这里存最小字符串，数据量非常大
inline void upd(string &dst, const string &cand, int &ok) {
    if (!ok || cand < dst) {
        dst = cand;
        ok = 1;
    }
}
inline void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    dp[1][1][0] = string(1, s[1][1]);
    ok[1][1][0] = 1;
    if (k >= 1 && s[1][1] != 'a') {
        dp[1][1][1] = "a";
        ok[1][1][1] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1) continue;
            char c = s[i][j];
            for (int t = 0; t <= k; t++) {
                // 1) 不改当前格：从上 / 左 (同 t) 来，加 c
                if (i > 1 && ok[i - 1][j][t]) {
                    string cand = dp[i - 1][j][t];
                    cand.push_back(c);
                    upd(dp[i][j][t], cand, ok[i][j][t]);
                }
                if (j > 1 && ok[i][j - 1][t]) {
                    string cand = dp[i][j - 1][t];
                    cand.push_back(c);
                    upd(dp[i][j][t], cand, ok[i][j][t]);
                }
                // 2) 改当前格为 'a'：从上 / 左 (t - 1) 来，加 'a'
                // 注意：这里不需要 c!='a'，因为允许浪费一次修改
                if (t >= 1) {
                    if (i > 1 && ok[i - 1][j][t - 1]) {
                        string cand = dp[i - 1][j][t - 1];
                        cand.push_back('a');
                        upd(dp[i][j][t], cand, ok[i][j][t]);
                    }
                    if (j > 1 && ok[i][j - 1][t - 1]) {
                        string cand = dp[i][j - 1][t - 1];
                        cand.push_back('a');
                        upd(dp[i][j][t], cand, ok[i][j][t]);
                    }
                }
            }
        }
    }
    string Ans;
    bool has = false;
    for (int t = 0; t <= k; t++) if (ok[n][n][t]) {
        if (!has || dp[n][n][t] < Ans) Ans = dp[n][n][t], has = true;
    }
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

空间优化

考虑 父指针 + rank（按层压缩） 的方式对空间进行压缩，同 浅谈棋盘类DP（二） 中的方案相同。

  • 不再存 dpi,j,tdp_{i, j, t} 的整条字符串本体 。
  • 只存它由哪一个父状态转移来（父指针），以及 它在这一层所有字符串中的字典序排名 rank 。

这样比较两个候选就从 比字符串 O(n)O(n) 变成 比二元组 O(1)O(1) 。

需要注意比较虽然时间复杂度降低了，但是每层还需要排序，所以时间复杂度并不能降低多少，只能降低 大量 string 拷贝 的时间复杂度。

空间降低规模

1）朴素 DP 存字符串

朴素版要存 dpi,j,tdp_{i, j, t} 的 整条字符串 ，长度大约是 i+j−1=O(n)i+j-1=O(n)。

  • 状态数：n2(k+1)n^2(k+1) 。
  • 每个状态一条长度 O(n)O(n) 的字符串。

所以字符总量级：

Θ(n2(k+1)⋅n)=Θ(n3k)\Theta(n^2(k+1)\cdot n) = \Theta(n^3k)

而且 std::string 还有额外的对象开销、capacity、分配器碎片等，实际更大。

2）rank + 父指针版：空间复杂度降到多少？

只存每个状态的 少量整数 ：

  • rki,j,trk_{i, j, t}：int（4B）
  • parDirparDir：1B
  • parModparMod：1B
  • parTparT：2B（用 unsigned short 足够，t≤kt\le k）

合起来大约 88 字节 / 状态（再加对齐可能到 8∼12B8 \sim 12B）。

状态数还是 n2(k+1)n^2(k+1)，所以空间：

Θ(n2k)\Theta(n^2k)

另外每一层收集的 vec 大小 ≤n(k+1)\le n(k+1)，只是临时的。

3）空间节省了多少倍？（最关键结论）

对比两者：

  • 朴素字符串版：Θ(n3k)\Theta(n^3k) 。
  • rank + 父指针：Θ(n2k)\Theta(n^2k) 。

所以空间 理论上降低了一个 nn 的量级 ：

n3kn2k=Θ(n)\frac{n^3k}{n^2k} = \Theta(n)

也就是大约省了 nn 倍 。

状态

$$dp_{i,j,t} \text{从 }(1,1)\text{ 走到 }(i,j)\text{，恰好修改 }t\text{ 次后能得到的字典序最小字符串} $$

但 不存 dpi,j,tdp_{i,j,t} 本体，只存：

  • rki,j,trk_{i, j, t}：该字符串在长度为 i+j−1i+j-1 的所有状态字符串中的 字典序排名 （越小越好）

  • parDiri,j,tparDir_{i, j, t}：父方向（上 / 左）。

  • parTi,j,tparT_{i, j, t}：父状态的 tt 。

  • parModi,j,tparMod_{i, j, t}：当前格是否使用一次修改（改成 'a'）。

为什么只用 (父rank, 当前字符) 就能比较新字符串

当前层长度为 L=i+j−1L=i+j-1。任一转移得到的字符串形如：

S=Sparent+chS = S_{\text{parent}} + ch

其中 SparentS_{\text{parent}} 长度为 L−1L-1，它在上一层已经有排名 rkparentrk_{parent}。

对两个候选：

S1=P1+c1,S2=P2+c2S_1 = P_1 + c_1,\quad S_2 = P_2 + c_2

它们字典序比较等价于先比前缀 P1P_1 和 P2P_2 ，若前缀相同再比最后一位。因为 rkparentrk_{parent} 就表示 PP 的字典序大小，所以只要比较二元组：

(rk(P),,c)(\text{rk}(P),, c)

就等价于比较完整字符串 SS 。

因此我们对每个状态 (i,j,t)(i,j,t) 只需要选一个最小的 签名 ：

keyi,j,t=(rkparent,,ch)key_{i,j,t} = (\text{rk}_{parent},, ch)

按层（对角线）做 rank 压缩

同一层是固定 i+j=sumi+j=\text{sum}（字符串长度固定为 sum−1sum-1 ）。

流程：

  1. 对本层所有状态 (i,j,t)(i,j,t)，用上一层的 rkrk 选出最小 key=(rkparent,ch)key=(rk_{parent}, ch) ，并记录父指针。
  2. 把本层所有可达状态的 keykey 收集起来排序，相同 keykey 给同一个 rankrank ，不同 key rank 递增。
    • 这就是 每层压缩 。
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 50 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Node {
    int pr; char ch;
    int i, j, t;
    bool operator<(const Node& o) const {
        if (pr != o.pr) return pr < o.pr;
        return ch < o.ch;
    }
};
// rk[i][j][t]：该状态字符串在本层的排名（越小越好），不可达为 INF
// 父指针：parDir 0 = 上, 1 = 左；parMod 0 = 不改, 1 = 改成 'a'；parT 父的 t
int n, k, rk[N][N][N * N], parT[N][N][N * N];
char s[N][N], parDir[N][N][N * N], parMod[N][N][N * N];  
string dp[N][N][N * N];
inline void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    // sum = i + j，sum = 2 是(1, 1)，字符串长度 = sum - 1
    auto G = [&](int i, int j) -> char {return s[i][j];};
    for (int sum = 2; sum <= 2 * n; sum++) {
        vector<Node> vec;
        // 枚举本层所有 (i,j)
        int il = max(1, sum - n);
        int ir = min(n, sum - 1);
        for (int i = il; i <= ir; i++) {
            int j = sum - i;
            for (int t = 0; t <= k; t++) {
                int bestPr = inf;
                char bestCh = '{'; // 比 'z' 大
                unsigned char bestDir = 0, bestMod = 0;
                int bestPT = 0;
                auto relax = [&](int pr, char ch, unsigned char dir, unsigned char mod, int pt) {
                    if (pr == inf) return;
                    if (pr < bestPr || (pr == bestPr && ch < bestCh)) {
                        bestPr = pr; bestCh = ch;
                        bestDir = dir; bestMod = mod; bestPT = pt;
                    }
                };
                if (sum == 2) {
                    // (1, 1) 基础层：父 rank 视为0（空前缀）
                    // t = 0：不改 -> g[1][1]
                    // t >= 1：允许浪费修改，最优就是 'a'
                    if (t == 0) relax(0, G(1,1), 0, 0, 0);
                    else relax(0, 'a', 0, 1, 0);
                } else {
                    char c = G(i, j);
                    // 来自上：不改
                    if (i > 1) relax(rk[i - 1][j][t], c, 0, 0, t);
                    // 来自左：不改
                    if (j > 1) relax(rk[i][j - 1][t], c, 1, 0, t);
                    // 改当前格为 'a'：来自上 / 左且 t >= 1
                    if (t >= 1) {
                        if (i > 1) relax(rk[i - 1][j][t - 1], 'a', 0, 1, t - 1);
                        if (j > 1) relax(rk[i][j - 1][t - 1], 'a', 1, 1, t - 1);
                    }
                }
                if (bestPr != inf) {
                    parDir[i][j][t] = bestDir;
                    parMod[i][j][t] = bestMod;
                    parT[i][j][t] = (unsigned short)bestPT;
                    vec.push_back({bestPr, bestCh, i, j, t});
                }
            }
        }
        // 本层 rank 压缩
        sort(vec.begin(), vec.end());
        int curRank = 0;
        int lastPr = -1; char lastCh = 0;
        for (auto &nd : vec) {
            if (nd.pr != lastPr || nd.ch != lastCh) {
                curRank++;
                lastPr = nd.pr;
                lastCh = nd.ch;
            }
            rk[nd.i][nd.j][nd.t] = curRank;
        }
    }
    // 选答案：在 (n, n) 取 t <= k 中 rank 最小者
    int bestT = -1, bestR = inf;
    for (int t = 0; t <= k; t++) {
        if (rk[n][n][t] < bestR) {
            bestR = rk[n][n][t];
            bestT = t;
        }
    }
    // 回溯构造字符串
    int L = 2 * n - 1;
    string Ans(L, '?');
    int i = n, j = n, t = bestT;
    int pos = L - 1;
    while (!(i == 1 && j == 1)) {
        Ans[pos--] = (parMod[i][j][t] ? 'a' : G(i, j));
        int pt = parT[i][j][t];
        if (parDir[i][j][t] == 0) i--;
        else j--;
        t = pt;
    }
    // 起点字符（t > 0 表示我们在(1, 1)也选择了改成a / 浪费修改的那条最优定义）
    Ans[0] = (t > 0 ? 'a' : G(1, 1));
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

降低时间复杂度

很明显需要将 tt 这一个维度降低下来，虽然前面强调了很多遍了，这里还是在提一下：

字典序最小 = 尽可能让前面的字符越小越好 。

在这个题里，修改一个格子能把字符变成任意字母，但最优永远只会改成 'a'（最小字母）。所以修改的作用只有一种：

把路径前缀里的某些字符变成 'a'，从而让前缀更小。

那么策略必然是：

  1. 先把能变成 'a' 的前缀长度尽量拉长（这是字典序最关键的部分）；
  2. 一旦 'a' 前缀已经无法再延长（否则就更优了），后面就只能在剩下的格子里按字典序最小走（分层贪心）。

因此我们只需要知道：

到每个格子 (i,j)(i,j)，把从起点到这里这段前缀 全变成 'a' 最少要改几次。

这就变成一个 二维最短路 / DP 问题了。

总结

令

cost(i,j)=[si,j≠’a’]cost(i,j) = [s_{i,j}\ne \text{'a'}]

定义

$$dp_{i,j}=\min\{\text{把某条 }(1,1)\to(i,j)\text{ 路径上所有字符都变成 'a' 所需修改次数}\} $$

转移：

$$dp_{i,j} = \min(dp_{i-1,j}, dp_{i,j-1}) + cost(i,j) $$

这是 O(n2)O(n^2) 。

然后找能做到的最远步数：

best=max⁡{i+j−2∣dpi,j≤k}best = \max\{i+j-2 \mid dp_{i,j}\le k\}

这意味着答案的前缀可以做到 best+1best+1 个 'a' 。

分层贪心（BFS）补后缀：只留能达到最小前缀的状态集合

把所有满足

  • i+j−2=besti+j-2 = best

  • dpi,j≤kdp_{i,j}\le k

的格子作为当前集合 curcur（它们都能实现最优的 'a' 前缀）。

接下来重复：

  • 看 curcur 所有后继（右 / 下）的字符，取最小 bestcbestc

  • 答案加上 bestcbestc

  • nxtnxt 收集所有字符为 bestcbestc 的后继（去重）

  • cur=nxtcur = nxt

每个格子最多入集合几次（去重后总体 O(n2)O(n^2))，所以这部分也是 O(n2)O(n^2) 。

最终复杂度

  • 二维 dp：O(n2)O(n^2)

  • 分层贪心：O(n2)O(n^2)

总时间：

O(n2)\boxed{O(n^2)}

空间：

O(n2)\boxed{O(n^2)} 
#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
typedef long long LL;
const int N = 2e3 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, k, dp[N][N], vis[N][N], tim;
char s[N][N];
inline void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    // 1) dp[i][j]: 最少改多少次，使得 (1, 1) -> (i, j) 这段前缀全为 'a'
    for (int i = 0; i <= n; i++) dp[i][0] = dp[0][i] = inf;
    dp[1][1] = (s[1][1] != 'a');
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1) continue;
            int c = (s[i][j] != 'a');
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + c;
        }
    }
    int best = -1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dp[i][j] <= k) best = max(best, i + j - 2);
    string Ans;
    vector<PII> cur, nxt;
    if (best == -1) {
        // 只有当 k = 0 且 s[1][1] != 'a' 才会出现
        Ans.push_back(s[1][1]);
        cur.push_back({1, 1});
        best = 0; // 当前已确定到步数 0
    } else {
        Ans.assign(best + 1, 'a');
        // 收集 best 这条对角线上的所有可行点
        for (int i = 1; i <= n; i++) {
            int j = (best + 2) - i; // i + j - 2 = best => i + j = best + 2
            if (j < 1 || j > n) continue;
            if (dp[i][j] <= k) cur.push_back({i, j});
        }
    }
    // 2) 分层贪心补齐剩余字符
    tim = 1;
    for (int step = best; step < 2 * n - 2; step++) {
        char bestc = '{'; // 比 'z' 大
        for (auto &p : cur) {
            int x = p.fi, y = p.se;
            if (x + 1 <= n) bestc = min(bestc, s[x + 1][y]);
            if (y + 1 <= n) bestc = min(bestc, s[x][y + 1]);
        }
        Ans.push_back(bestc);
        tim++;
        nxt.clear();
        for (auto &p : cur) {
            int x = p.fi, y = p.se;
            if (x + 1 <= n && s[x + 1][y] == bestc && vis[x + 1][y] != tim) {
                vis[x + 1][y] = tim;
                nxt.push_back({x + 1, y});
            }
            if (y + 1 <= n && s[x][y + 1] == bestc && vis[x][y + 1] != tim) {
                vis[x][y + 1] = tim;
                nxt.push_back({x, y + 1});
            }
        }
        cur.swap(nxt);
    }
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}
4
已通过
0
题解被赞

0 条评论

目前还没有评论...
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  3. 京ICP备2024092232号-2
  4. 京公网安备图标 京公网安备11010802045784号
  5. DAMON THRONE