针对 P1140 相似基因，我们需要构造能够覆盖各种边界情况（如极短序列、极大差异序列、完全相同序列）的测试数据。由于题目规模较小（$N, M \le 100$），数据文件会非常精简，重点在于测试选手代码对负权值初始化和边界状态转移的处理。

该生成器集成标准 DP 算法，采用迭代写法，确保生成 .out 文件时既快又稳。

数据生成器 C++14 代码

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <random>
#include <algorithm>
#include <ctime>

using namespace std;

// 全局打分矩阵，用于生成标准答案
const int score_matrix[5][5] = {
    { 5, -1, -2, -1, -3}, // A
    {-1,  5, -3, -2, -4}, // C
    {-2, -3,  5, -2, -2}, // G
    {-1, -2, -2,  5, -1}, // T
    {-3, -4, -2, -1,  0}  // -
};

int get_id(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    if (c == 'T') return 3;
    return 4; // '-'
}

/**
 * 标准 DP 求解函数
 * 用于生成测试点的 .out 文件
 */
int solve(int n, string s1, int m, string s2) {
    // 1-based DP 数组，初始化为极小值
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1e9));
    
    dp[0][0] = 0;
    // 初始化第一列 (s1 对空)
    for (int i = 1; i <= n; ++i)
        dp[i][0] = dp[i-1][0] + score_matrix[get_id(s1[i-1])][4];
    // 初始化第一行 (s2 对空)
    for (int j = 1; j <= m; ++j)
        dp[0][j] = dp[0][j-1] + score_matrix[4][get_id(s2[j-1])];

    // 递推过程
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int c1 = dp[i-1][j-1] + score_matrix[get_id(s1[i-1])][get_id(s2[j-1])];
            int c2 = dp[i-1][j] + score_matrix[get_id(s1[i-1])][4];
            int c3 = dp[i][j-1] + score_matrix[4][get_id(s2[j-1])];
            dp[i][j] = max({c1, c2, c3});
        }
    }
    return dp[n][m];
}

/**
 * 随机碱基生成
 */
string gen_dna(int len, mt19937& rng) {
    string res = "";
    string bases = "ACGT";
    uniform_int_distribution<int> dist(0, 3);
    for (int i = 0; i < len; ++i) res += bases[dist(rng)];
    return res;
}

/**
 * 生成测试用例主逻辑
 */
void create_case(int id, int n, int m, int type) {
    mt19937 rng(time(0) + id);
    string s1, s2;

    if (type == 0) { // 极小数据
        s1 = gen_dna(n, rng);
        s2 = gen_dna(m, rng);
    } else if (type == 1) { // 完全相同
        s1 = gen_dna(n, rng);
        s2 = s1;
        m = n;
    } else if (type == 2) { // 长度悬殊
        s1 = gen_dna(n, rng);
        s2 = gen_dna(m, rng);
    } else if (type == 3) { // 重复字符 (易产生累计负分)
        for(int i=0; i<n; i++) s1 += 'A';
        for(int i=0; i<m; i++) s2 += 'C';
    } else { // 随机大数据
        s1 = gen_dna(n, rng);
        s2 = gen_dna(m, rng);
    }

    // 写入 .in
    string in_name = to_string(id) + ".in";
    ofstream fin(in_name);
    fin << n << " " << s1 << "\n" << m << " " << s2 << endl;
    fin.close();

    // 写入 .out
    string out_name = to_string(id) + ".out";
    ofstream fout(out_name);
    fout << solve(n, s1, m, s2) << endl;
    fout.close();

    cout << "Case " << id << " [N=" << n << ", M=" << m << "] generated." << endl;
}

int main() {
    // 1-2: 极小边界
    create_case(1, 1, 1, 0);
    create_case(2, 2, 3, 0);

    // 3-4: 相同与差异
    create_case(3, 100, 100, 1); // 全等
    create_case(4, 100, 100, 3); // 全 A vs 全 C (测试负权累加)

    // 5-6: 长度差异极限
    create_case(5, 100, 1, 2);
    create_case(6, 1, 100, 2);

    // 7-10: 随机极限情况
    create_case(7, 50, 50, 4);
    create_case(8, 80, 90, 4);
    create_case(9, 100, 100, 4);
    create_case(10, 100, 100, 4);

    return 0;
}

数据设计与优化说明

1. 针对性场景设计

• Case 1 & 2：最小规模测试。很多选手在处理 n=1 时下标容易溢出或逻辑跑不进循环。
• Case 3 (完全相同)：测试匹配成功的 score=5 是否能被正确选取。
• Case 4 (极端负权)：AAAA... 与 CCCC... 匹配，得分为大量的 -1 或 -3。这能有效测试选手是否正确初始化了 dp 数组（如果初始化为 0，则此点必错）。
• Case 5 & 6 (长度悬殊)：一个序列跑完了，另一个序列还剩很多。测试对“第一行/第一列”初始化的正确性。

2. 生成效率与安全性

• 计算复杂度：$N=100$ 规模下，DP 计算量仅为 $10^4$。生成 10 个测试点即便包含磁盘 I/O 也只需不到 0.1 秒。
• 内存与栈安全：
  • 使用 std::vector 动态分配内存。
  • 采用迭代 DP 逻辑，完全排除了递归深度导致的爆栈隐患。
  • 逻辑中不存在除法，从根本上杜绝了 Floating point exception。

3. 文件大小控制

• 输入文件包含两个 100 字符的字符串，大小约为 0.2 KB。
• 10 个测试点的总大小不到 5 KB。远低于题目要求的 2 MB，非常适合在 OJ 平台上快速分发。

4. OJ 部署提示

• 时间限制建议：设置为 1.0s（实际上 DP 跑 100x100 只需要几毫秒）。
• 内存限制建议：设置为 128MB。
• 核心逻辑检查：重点检查选手是否处理了 dp[i][0] 和 dp[0][j]。如果没有初始化这两项，程序在处理第 5、6 号测试点时会输出错误结果。

这份数据生成器产生的测试集既能保护基础分，又能精准卡掉逻辑不严密的算法。你可以直接编译运行生成数据包。

你好！作为金牌教练，我非常强调对状态转移物理意义的理解。

“相似基因”这道题是线性 DP 的经典进阶。它与“编辑距离”最大的不同点在于：

1. 权值自定义：不再是统一的 $+1$，而是查表获取分值。
2. 负值风险：得分可能是负数，这要求我们在初始化和求最大值时必须非常小心。

下面我为你展示从“暴力递归”到“最优递推”的进化过程。

准备工作：公共映射表

为了提高效率，我们先定义好碱基到索引的映射。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 全局打分矩阵：A=0, C=1, G=2, T=3, -=4
int score_map[5][5] = {
    { 5, -1, -2, -1, -3}, // A
    {-1,  5, -3, -2, -4}, // C
    {-2, -3,  5, -2, -2}, // G
    {-1, -2, -2,  5, -1}, // T
    {-3, -4, -2, -1,  0}  // - (注意：题目中-与-不对应，此处0仅占位)
};

// 字符转索引辅助函数
int get_idx(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    if (c == 'T') return 3;
    return 4; // '-'
}

代码讲解

你好！作为金牌教练，我非常强调“模型演进”的思考方式。相似基因这道题是**线性动态规划（Linear DP）**中的经典模型——双序列比对。

这道题的难点在于：

1. 权值不是固定常数：需要通过打分矩阵查询。
2. 初始化陷阱：得分可能为负，不能简单初始化为 0。
3. 边界状态：第一行和第一列的转移逻辑代表了一个序列与空位的完全匹配。

以下是三个版本的完整代码演进：

版本一：简单暴力递归（指数级复杂度）

思路： 从两个字符串的末尾开始，尝试三种可能的匹配方式：(字符对字符)、(A串字符对空)、(B串字符对空)。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

// 打分矩阵映射表
int score_table[5][5] = {
    {5, -1, -2, -1, -3}, // A
    {-1, 5, -3, -2, -4}, // C
    {-2, -3, 5, -2, -2}, // G
    {-1, -2, -2, 5, -1}, // T
    {-3, -4, -2, -1, 0}  // -
};

int get_idx(char c) {
    if (c == 'A') return 0; if (c == 'C') return 1;
    if (c == 'G') return 2; if (c == 'T') return 3;
    return 4; // 代表 '-'
}

// 递归函数：计算 s1 前 i 个和 s2 前 j 个的最大相似度
long long dfs(const string& s1, const string& s2, int i, int j) {
    // 边界条件：一个串已经消耗完，另一个串剩下的只能匹配 '-'
    if (i == 0 && j == 0) return 0;
    if (i == 0) return dfs(s1, s2, 0, j - 1) + score_table[4][get_idx(s2[j - 1])];
    if (j == 0) return dfs(s1, s2, i - 1, 0) + score_table[get_idx(s1[i - 1])][4];

    // 情况 1: s1[i-1] 匹配 s2[j-1]
    long long res1 = dfs(s1, s2, i - 1, j - 1) + score_table[get_idx(s1[i - 1])][get_idx(s2[j - 1])];
    // 情况 2: s1[i-1] 匹配 '-'
    long long res2 = dfs(s1, s2, i - 1, j) + score_table[get_idx(s1[i - 1])][4];
    // 情况 3: s2[j-1] 匹配 '-'
    long long res3 = dfs(s1, s2, i, j - 1) + score_table[4][get_idx(s2[j - 1])];

    return max({res1, res2, res3});
}

int main() {
    int n, m;
    string s1, s2;
    if (!(cin >> n >> s1 >> m >> s2)) return 0;
    // 暴力版本处理长度 > 15 的数据就会严重超时
    cout << dfs(s1, s2, n, m) << endl;
    return 0;
}

版本二：记忆化搜索（最优时间，标准空间）

思路： 在暴力递归的基础上增加一个 memo 数组。如果当前 (i, j) 状态已经计算过，直接返回结果，消除大量重复子问题。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 105;
const long long INF = 1e15;
long long memo[MAXN][MAXN];
bool vis[MAXN][MAXN];

int score_table[5][5] = {
    {5, -1, -2, -1, -3}, {-1, 5, -3, -2, -4}, {-2, -3, 5, -2, -2}, {-1, -2, -2, 5, -1}, {-3, -4, -2, -1, 0}
};

int get_idx(char c) {
    if (c == 'A') return 0; if (c == 'C') return 1;
    if (c == 'G') return 2; if (c == 'T') return 3;
    return 4;
}

long long solve(const string& s1, const string& s2, int i, int j) {
    if (i == 0 && j == 0) return 0;
    if (vis[i][j]) return memo[i][j];

    long long res = -INF;
    if (i == 0) res = solve(s1, s2, 0, j - 1) + score_table[4][get_idx(s2[j - 1])];
    else if (j == 0) res = solve(s1, s2, i - 1, 0) + score_table[get_idx(s1[i - 1])][4];
    else {
        // 三选一决策
        res = max({
            solve(s1, s2, i - 1, j - 1) + score_table[get_idx(s1[i - 1])][get_idx(s2[j - 1])],
            solve(s1, s2, i - 1, j) + score_table[get_idx(s1[i - 1])][4],
            solve(s1, s2, i, j - 1) + score_table[4][get_idx(s2[j - 1])]
        });
    }

    vis[i][j] = true;
    return memo[i][j] = res;
}

int main() {
    int n, m;
    string s1, s2;
    if(!(cin >> n >> s1 >> m >> s2)) return 0;
    cout << solve(s1, s2, n, m) << endl;
    return 0;
}

版本三：递推 DP + 空间优化（NOIP 满分版）

思路： 将递归改为迭代（递推），并利用滚动数组将空间复杂度从 $O(NM)$ 降低到 $O(M)$。这是应对大数据规模时的终极武器。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 打分矩阵映射
int score_m[5][5] = {
    {5, -1, -2, -1, -3},
    {-1, 5, -3, -2, -4},
    {-2, -3, 5, -2, -2},
    {-1, -2, -2, 5, -1},
    {-3, -4, -2, -1, 0}
};

int get_id(char c) {
    if (c == 'A') return 0; if (c == 'C') return 1;
    if (c == 'G') return 2; if (c == 'T') return 3;
    return 4;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    string s1, s2;
    if (!(cin >> n >> s1 >> m >> s2)) return 0;

    // dp[j] 表示当前行（i），dp_prev[j] 表示上一行（i-1）
    // 【陷阱】初始化必须为极小值，因为相似度可能是负数
    const int INF = 1e9;
    vector<int> dp_prev(m + 1, -INF);
    vector<int> dp_curr(m + 1, -INF);

    // 1. 初始化 dp_prev (即 i=0 的情况)
    dp_prev[0] = 0;
    for (int j = 1; j <= m; ++j) {
        dp_prev[j] = dp_prev[j - 1] + score_m[4][get_id(s2[j - 1])];
    }

    // 2. 递推开始
    for (int i = 1; i <= n; ++i) {
        // dp_curr[0] 表示当前 i 下，j=0 的情况（s1 的前 i 个对应空）
        dp_curr[0] = dp_prev[0] + score_m[get_id(s1[i - 1])][4];
        
        for (int j = 1; j <= m; ++j) {
            // 三种转移来源
            int match = dp_prev[j - 1] + score_m[get_id(s1[i - 1])][get_id(s2[j - 1])];
            int gap_s2 = dp_prev[j] + score_m[get_id(s1[i - 1])][4];
            int gap_s1 = dp_curr[j - 1] + score_m[4][get_id(s2[j - 1])];
            
            dp_curr[j] = max({match, gap_s2, gap_s1});
        }
        // 滚动数组更新
        dp_prev = dp_curr;
    }

    cout << dp_prev[m] << endl;

    return 0;
}

复杂度分析与性能思考

1. 时间复杂度

• 分析：三个版本在本质逻辑上都是填一张 $N \times M$ 的表。递推版本通过双重循环，时间复杂度稳定在 $O(N \times M)$。
• 规模：$100 \times 100 = 10^4$ 次运算，在 1.0s 时限内极其充裕（可处理到 $N, M \le 5000$）。

2. 空间复杂度

• 二维版：$O(N \times M)$，约 $40\text{ KB}$。
• 滚动数组版：$O(M)$，约 $0.8\text{ KB}$。
• 建议：在 NOI 竞赛中，如果 $N, M \le 1000$，建议直接使用二维数组，代码可读性更强且不易写错下标。

3. 性能优化建议

• 打分查表：不要在循环里用 if-else 判断字符，预先映射成数字查表。
• 初始化：这是本题最容易丢分的地方。第一行和第一列不是全 0，而是累加空位惩罚分。
• 负无穷大：使用 -1e9 或 INT_MIN / 2。不要直接用 INT_MIN，否则两个 INT_MIN 相加会产生溢出，导致 max 判断失效。

总结：读题时的“黄金眼”

• 一旦看到 “两个序列比对”、“插入空位”、“最大化得分”。
• 立刻反应：线性二维 DP。
• 立刻思考：状态来源是三个点——左、上、左上。
• 立刻检查：打分矩阵里有没有负数？如果有，初始化必须负无穷！

加油，同学！稳住这两题，你的序列 DP 就已经算入门了！