阿西莫夫的解题指南

这是一道典型的 区间动态规划（Interval DP） 题目。

1. 状态定义

我们需要定义一个小问题，然后逐步扩大范围。 令 $dp[i][j]$ 表示：字符串从下标 $i$ 到 $j$ 这一段子串（$S[i \dots j]$），最多能形成多少对配对。

2. 状态转移方程

对于区间 $[i, j]$，我们考虑左端点 $i$ 的去留：

1. 情况 A：$i$ 不参与配对。 那么最大配对数就等于去掉 $i$ 后的结果：

   $$dp[i][j] = dp[i+1][j]$$

2. 情况 B：$i$ 参与配对。 $i$ 必须和区间内的一个 $k$ 配对（其中 $i < k \le j$）。

   • 首先，检查 $S[i]$ 和 $S[k]$ 是否能配对（A-U 或 C-G）。
   • 其次，检查距离是否合法（题目要求相邻不能配，即 $k > i+1$）。
   • 如果配对成功，那么整个大区间就被分成了两部分：
     1. 夹在 $i$ 和 $k$ 之间的部分：$dp[i+1][k-1]$。
     2. $k$ 右边的部分：$dp[k+1][j]$。
     3. 加上 $i, k$ 这一对，贡献 +1。
   • 方程：$$ dp[i][j] = \max(dp[i][j], \ 1 + dp[i+1][k-1] + dp[k+1][j]) $$

3. 计算顺序

区间 DP 的核心是先枚举长度，再枚举起点。 我们要先算出短区间的答案，才能推导出长区间的答案。

阿西莫夫的点评

1. 为什么是 DP？ 如果用贪心算法（遇到配对就连），很容易陷入局部最优。例如 GGCA CC，如果第一个 G 和第一个 C 配了，中间的 G-C 就被切断了。只有 DP 的全局搜索才能找到嵌套的最优解。
2. 生物学意义： 这就是著名的 Nussinov 算法 的简化版。它是计算生物学中最基础的算法之一。通过这道题，学生不仅练习了区间 DP，还触碰到了生命科学计算的基石。

User 为什么这个标准解答我输入ACGU和AUGGC跑出来都是1？

你好，我是阿西莫夫。

非常敏锐的观察！你的测试结果是正确的，是我之前的代码中为了模拟“生物学真实性”加了一个额外的限制，导致了结果与直观的“最大匹配数”不符。

问题原因分析

在之前的代码中，有一行代码是这样的：

if (k == i + 1) continue; // 题目设定: 相邻不能配对

原因：在真实的生物物理学中，RNA 链条是有刚性的，无法在相邻的两个碱基之间发生“180度急转弯”来配对（通常至少中间要隔 3 个碱基形成发夹环）。 结果：

• 对于 ACGU：中间的 C 和 G 是相邻的。旧代码禁止它们配对，所以只剩外面的 A-U，结果为 1。
• 对于 AUGGC：开头的 A 和 U 是相邻的。旧代码禁止它们配对，只剩后面的 G-C（中间隔了 G），结果为 1。

但在**信息学算法竞赛（OI）**的基础题目中，通常为了简化模型，考察纯粹的“最大匹配”，是允许相邻碱基配对的。

修正方案

我们需要删除“相邻不能配对”的限制。这样：

• ACGU：C-G（相邻）配对 + A-U（嵌套）配对 = 2。
• AUGGC：A-U（相邻）配对 + G-C（相隔）配对 = 2。

修正后的 C++ 标准解答 (允许相邻配对)

这份代码会输出你期望的 2。

/**
 * 题目: RNA 的折叠艺术 (The RNA Folder) - 最大匹配版
 * 作者: Isaac Asimov (AI)
 * 修正: 移除了“相邻不能配对”的物理限制，追求纯数学上的最大匹配数。
 */

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

using namespace std;

// 判断碱基是否配对
bool match(char a, char b) {
    if (a == 'A' && b == 'U') return true;
    if (a == 'U' && b == 'A') return true;
    if (a == 'G' && b == 'C') return true;
    if (a == 'C' && b == 'G') return true;
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    if (!(cin >> s)) return 0;

    int n = s.length();
    
    // dp[i][j] 表示子串 s[i...j] 的最大配对数
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // 1. 枚举区间长度 len 
    // (从 2 开始，因为至少要 2 个碱基才能配对)
    for (int len = 2; len <= n; len++) {
        // 2. 枚举左端点 i
        for (int i = 0; i <= n - len; i++) {
            // 计算右端点 j
            int j = i + len - 1;

            // 策略 1: i 不参与配对
            dp[i][j] = dp[i + 1][j];

            // 策略 2: i 参与配对，尝试寻找配对对象 k
            // 遍历 i 右边的所有可能的 k
            for (int k = i + 1; k <= j; k++) {
                
                // 【核心修正】：删除了 "if (k == i + 1) continue;"
                // 现在允许相邻的碱基配对 (如 A-U)
                
                if (match(s[i], s[k])) {
                    // 如果 i 和 k 配对：
                    // 1 (这一对)
                    // + dp[i+1][k-1] (夹在中间的部分)
                    // + dp[k+1][j]   (右边剩下的部分)
                    
                    int inside = (i + 1 <= k - 1) ? dp[i + 1][k - 1] : 0;
                    int outside = (k + 1 <= j) ? dp[k + 1][j] : 0;
                    
                    dp[i][j] = max(dp[i][j], 1 + inside + outside);
                }
            }
        }
    }

    cout << dp[0][n - 1] << endl;

    return 0;
}

修正后的数据生成器

为了配合新的逻辑（允许相邻配对），数据生成器中的标准解答部分也必须同步更新，否则生成的 .out 文件会和上面的代码跑出来的结果不一致。

/**
 * Project: The RNA Folder (Data Generator) - Fixed
 * Update: Allowed adjacent pairing logic for Solver.
 */

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

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑 (已修正)
// ==========================================
class Solution {
    bool match(char a, char b) {
        if (a == 'A' && b == 'U') return true;
        if (a == 'U' && b == 'A') return true;
        if (a == 'G' && b == 'C') return true;
        if (a == 'C' && b == 'G') return true;
        return false;
    }
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        string s;
        cin >> s;
        int n = s.length();
        // 初始化 DP 表
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                // 默认不配对 i
                dp[i][j] = dp[i + 1][j];
                
                // 尝试配对 i 和 k
                for (int k = i + 1; k <= j; k++) {
                    // 这里去掉了 continue，允许相邻配对
                    if (match(s[i], s[k])) {
                        int inside = (i + 1 <= k - 1) ? dp[i + 1][k - 1] : 0;
                        int outside = (k + 1 <= j) ? dp[k + 1][j] : 0;
                        dp[i][j] = max(dp[i][j], 1 + inside + outside);
                    }
                }
            }
        }
        cout << dp[0][n - 1] << endl;
        
        cin.close();
        cout.close();
        cout << "Generated: " << out_file << endl;
    }
};

// ==========================================
// Part 2: 数据生成逻辑 (保持不变)
// ==========================================
mt19937 rng(2025);

int rand_int(int min, int max) {
    uniform_int_distribution<int> dist(min, max);
    return dist(rng);
}

char rand_base() {
    string bases = "AUGC";
    return bases[rand_int(0, 3)];
}

char complement(char c) {
    if (c == 'A') return 'U';
    if (c == 'U') return 'A';
    if (c == 'G') return 'C';
    if (c == 'C') return 'G';
    return c;
}

void generate_input(int case_id) {
    string filename = to_string(case_id) + ".in";
    ofstream fout(filename);

    string s = "";
    int n;

    // 样例复现
    if (case_id == 1) { s = "ACGU"; }
    else if (case_id == 2) { s = "AUGGC"; }
    else if (case_id == 3) { s = "GGGAAAUCC"; }
    else if (case_id <= 7) n = rand_int(10, 50);
    else n = rand_int(100, 200);

    if (case_id > 3) {
        if (case_id % 3 == 0) {
            // 回文结构 (强配对)
            int half = n / 2;
            string left = "";
            for(int i=0; i<half; i++) left += rand_base();
            string right = "";
            for(int i=half-1; i>=0; i--) right += complement(left[i]);
            s = left + right;
        } else {
            // 随机
            for (int i = 0; i < n; i++) s += rand_base();
        }
    }

    fout << s << endl;
    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating RNA Data (Fixed Logic) ---" << endl;
    
    Solution solver;
    for (int i = 1; i <= 10; i++) {
        generate_input(i);
        string in = to_string(i) + ".in";
        string out = to_string(i) + ".out";
        solver.solve(in, out);
    }
    cout << "--- Done! ---" << endl;
    return 0;
}

再次感谢你的指正。科学的道路就是不断 debug 的过程。