数据生成器 (Generator)

此生成器已修正，确保生成的第 2 组数据（样例 2）与题目描述完全一致，产出正确的 .out 文件。

请保存为 gen_lysosome_fixed.cpp 并运行。

/**
 * Project: Lysosome Recycling (Fixed Generator)
 * Author: Isaac Asimov (AI)
 * Fix: Sample 2 logic updated to match problem description.
 */

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

using namespace std;

// ==========================================
// Part 1: 标准解答逻辑
// ==========================================
class Solution {
public:
    void solve(string in_file, string out_file) {
        ifstream cin(in_file);
        ofstream cout(out_file);
        if (!cin.is_open()) return;

        int k; cin >> k;
        map<string, int> table;
        for(int i=0; i<k; i++){
            string n; int e; cin >> n >> e;
            table[n] = e;
        }
        string s; cin >> s;
        
        long long total_e = 0;
        string tmp = "";
        bool open = false;
        for(char c : s) {
            if(c=='[') { open=true; tmp=""; }
            else if(c==']') {
                if(table.count(tmp)) total_e += table[tmp];
                open=false;
            }
            else if(open) tmp += c;
        }

        int n; cin >> n;
        // 动态开数组，确保安全
        vector<long long> dp(total_e + 1, 0);
        for(int i=0; i<n; i++){
            int w, v; cin >> w >> v;
            for(int j=total_e; j>=w; j--)
                dp[j] = max(dp[j], dp[j-w] + v);
        }
        cout << dp[total_e] << 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);
}

vector<string> waste_dict = {"Mito", "Ribo", "Prot", "Lipid", "Sugar", "DNA", "RNA", "Virus", "Bacteria", "Toxin"};

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

    int k;

    // 1. 生成回收表
    if (case_id == 1) {
        // 样例 1
        fout << "3\nMito 50\nRibo 20\nProt 5" << endl;
        fout << "[Mito][Ribo][Prot][Prot]" << endl;
        fout << "3\n40 60\n50 80\n30 40" << endl;
        fout.close();
        return;
    }
    
    if (case_id == 2) {
        // 样例 2 (修正版)
        fout << "1\nVirus 100" << endl;
        fout << "[Virus][Unknown][Virus]" << endl;
        fout << "2\n100 10\n200 50" << endl;
        fout.close();
        return;
    }

    // 常规随机数据生成
    k = rand_int(3, 10);
    fout << k << endl;
    
    map<string, int> current_table;
    for(int i=0; i<k; i++) {
        string name = waste_dict[i];
        int val = rand_int(5, 50);
        fout << name << " " << val << endl;
        current_table[name] = val;
    }

    // 生成字符串
    string s = "";
    int items = rand_int(10, 50);
    for(int i=0; i<items; i++) {
        s += "[";
        if (rand_int(1, 100) <= 80) { // 80% 有效
            auto it = current_table.begin();
            advance(it, rand_int(0, k-1));
            s += it->first;
        } else {
            s += "Unknown";
        }
        s += "]";
    }
    fout << s << endl;

    // 生成任务
    int n = rand_int(10, 50);
    fout << n << endl;
    for(int i=0; i<n; i++) {
        fout << rand_int(10, 100) << " " << rand_int(10, 200) << endl;
    }

    fout.close();
}

int main() {
    ios_base::sync_with_stdio(false);
    cout << "--- Generating Lysosome Data (Fixed) ---" << 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;
}

C++ 标准解答 (NOIP C++14)

/**
 * 题目: 溶酶体的“回收与重造” (Recycling & Rebuilding)
 * 作者: Isaac Asimov (AI)
 * 知识点: std::map, String Parsing, 0/1 Knapsack
 */

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

using namespace std;

// 背包 DP 数组
// 考虑到 S 最长 1000，假设每个物品最大能量 200，总能量可达 200,000
// 开大一点防止越界
int dp[200005]; 

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

    // --- 第一阶段：回收 (建立映射) ---
    int k;
    cin >> k;

    map<string, int> recycle_table;
    for (int i = 0; i < k; i++) {
        string name;
        int energy;
        cin >> name >> energy;
        recycle_table[name] = energy;
    }

    // --- 解析自噬小泡字符串 ---
    string s;
    cin >> s;

    int total_energy = 0;
    string temp_name = "";
    bool capturing = false;

    // 遍历字符串，提取 [...] 中的内容
    for (char c : s) {
        if (c == '[') {
            capturing = true;
            temp_name = "";
        } else if (c == ']') {
            capturing = false;
            // 查表，如果存在则累加能量
            if (recycle_table.count(temp_name)) {
                total_energy += recycle_table[temp_name];
            }
        } else {
            if (capturing) temp_name += c;
        }
    }

    // --- 第二阶段：重造 (背包 DP) ---
    int n;
    cin >> n;

    // 初始化 dp 数组 (全局已自动为0)
    // 如果是多次询问需 memset

    for (int i = 0; i < n; i++) {
        int w, v;
        cin >> w >> v;
        // 0/1 背包倒序遍历
        // 注意遍历下界是 w
        for (int j = total_energy; j >= w; j--) {
            dp[j] = max(dp[j], dp[j - w] + v);
        }
    }

    cout << dp[total_energy] << endl;

    return 0;
}

阿西莫夫的点评

1. 分层处理： 这道题强迫学生将问题拆解。如果不先把字符串解析好算出总能量 $E$，后续的背包 DP 就无从谈起。这种**“预处理 + 核心算法”**的模式是复杂编程题的雏形。
2. 数据结构的组合： Map 解决了“这是什么东西”的问题（查找），Array (DP数组) 解决了“怎么分配”的问题（优化）。这是数据结构与算法的有机结合。