算法思想

首先预处理书名，提取纯字母序列并按字典序排序；然后采用动态规划，定义状态dp[j][k]表示选j本书且最后一本为第k本时的最大价值，通过遍历已选数量、当前书籍和前一本书，检查字符冲突后更新状态；接着利用前驱数组回溯选取的书籍索引；最后按要求输出数量、总价值和书名。核心是通过动态规划处理约束条件下的组合优化，利用预处理和有序性提升效率。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cctype>
#include <climits>
#include <map>
#include <sstream>

using namespace std;

struct Book {
    int value;
    string title;
    string normalized;
};

vector<Book> books;
vector<vector<int> > dp;
vector<vector<int> > prev_book;
int max_total = 0;
vector<int> best_sequence;

// 预处理标题，移除非字母字符并转为小写
string normalize_title(const string& title) {
    string normalized;
    for (size_t i = 0; i < title.size(); ++i) {
        char c = title[i];
        if (isalpha(c)) {
            normalized += tolower(c);
        }
    }
    return normalized;
}

// 检查两个标准化后的标题是否有相同位置的相同字母
bool has_conflict(const string& a, const string& b) {
    int len = min(a.size(), b.size());
    for (int i = 0; i < len; ++i) {
        if (a[i] == b[i]) {
            return true;
        }
    }
    return false;
}

// 比较函数对象，用于排序
struct BookCompare {
    bool operator()(const Book& a, const Book& b) const {
        return a.title < b.title;
    }
};

void solve() {
    int n = books.size();
    if (n == 0) return;

    // 按标题排序
    sort(books.begin(), books.end(), BookCompare());

    // 初始化DP表
    dp.assign(n, vector<int>(10, 0));
    prev_book.assign(n, vector<int>(10, -1));

    // 初始状态：每本书单独作为序列的第一个
    for (int i = 0; i < n; ++i) {
        dp[i][0] = books[i].value;
    }

    // 动态规划填表
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (!has_conflict(books[j].normalized, books[i].normalized)) {
                for (int k = 0; k < 9; ++k) {
                    if (dp[j][k] > 0 && dp[j][k] + books[i].value > dp[i][k+1]) {
                        dp[i][k+1] = dp[j][k] + books[i].value;
                        prev_book[i][k+1] = j;
                    }
                }
            }
        }
    }

    // 找到最大值
    max_total = 0;
    int last_book = -1, last_pos = -1;
    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < 10; ++k) {
            if (dp[i][k] > max_total) {
                max_total = dp[i][k];
                last_book = i;
                last_pos = k;
            }
        }
    }

    // 回溯找到序列
    best_sequence.clear();
    while (last_book != -1 && last_pos >= 0) {
        best_sequence.push_back(last_book);
        last_book = prev_book[last_book][last_pos];
        last_pos--;
    }
    reverse(best_sequence.begin(), best_sequence.end());
}

int string_to_int(const string& s) {
    istringstream iss(s);
    int value;
    iss >> value;
    return value;
}

int main() {
    int N;
    cin >> N;
    cin.ignore(); // 忽略第一行后面的换行符

    for (int i = 0; i < N; ++i) {
        string line;
        getline(cin, line);
        
        size_t space_pos = line.find(' ');
        int value = string_to_int(line.substr(0, space_pos));
        string title = line.substr(space_pos + 1);
        
        string normalized = normalize_title(title);
        Book book;
        book.value = value;
        book.title = title;
        book.normalized = normalized;
        books.push_back(book);
    }

    solve();

    // 输出结果
    cout << best_sequence.size() << endl;
    cout << max_total << endl;
    for (size_t i = 0; i < best_sequence.size(); ++i) {
        cout << books[best_sequence[i]].title << endl;
    }

    return 0;
}