原题
特别鸣谢：
– 三水-提供思路
– zbj-大部分的代码实现

题意

• 输入的第一行将包括两个整数，第一个是字符串的数量，第二个是每个字符串的长度。
  注意：由于保证给定的所有字符串等长，所以不会有abb + bb得到回文串的可能性。
• 第二行起，将是一个字符串和一个整数
  注意：一个字符串可以出现很多遍，且具有不同的(可能负的)权值
• 要求：
  输出由给定的字符串可以组合出的所有回文串中最大的权值和(将组成回文串用到的字串的权值加起来)。

解题

分析

对于任何字符串，要么它不能自回文，因此只能与其对应的回文串成对出现；要么能自回文，可以出现在中间位置，也可以成对出现。
那么对于任何特定的非自回文字符串及其逆序串就只需决定是否采用而不需要考虑其具体顺序。
但是回文串就要考虑谁在中间的问题。
进一步的，由于相同的字符串用哪一个都没关系，所以应当从相同字符串的权值中优先取最大的数，所以使用priority_pueuel来记录每个字符串对应的权值。

答题

因此，对于非回文串及其子串，应用以下代码

//mp存储非回文串的信息
//数据存到字符串与其逆序串中字典序较大的那一个的名下
//q1，q2是俩优先队列，分别存储这个字符串和其逆序串的信息
    for (auto it = mp.begin(); it != mp.end(); ++it)//挑选可以成对的非自回文串
    {
        while (!(it->second).q1.empty() && !(it->second).q2.empty() && (it->second).q1.top() + (it->second).q2.top() > 0)
            //如果优先队列都不为空且两边的top加起来大于0就可以选中，否则抛弃。
        {
            ans += (it->second).q1.top() + (it->second).q2.top();
            (it->second).q1.pop();(it->second).q2.pop();
        }
    }

对于回文串，大体上也如非回文串处理，但是要注意，由于可以放中间位置，所以把谁放进去，要不要放进去都要好好考虑一下。

//mp2存储回文串的信息，是个string到优先队列的map
    for (auto it = mp2.begin(); it != mp2.end(); ++it)//挑选必然成对的自回文串
    {
        while ((it->second).size() >= 2 && (it->second).top() > 0)
        {
            long long a = (it->second).top();(it->second).pop();
            long long b = (it->second).top();(it->second).pop();
            if (a > 0 && b > 0)//如果队列里前两个都大于0，必然可以选择
            {
                ans += a + b;
            }
            else
            {
                (it->second).push(a);(it->second).push(b);
                break;
            }
        }
    }

然后，剩下的回文串只有三种类型：
1. 前两个的和大于0，但是后一个为负值。
2. 只剩一个权值了。
3. 前两个的和小于0，但前一个为正值。

很明显，对于第一种情况，成对选择是可能的情况，但是相比于将其放入中间，有值为后一个权的绝对值的损失。
对于第二种或者第三种情况，成对选择是不可能的，如果不将其放入中间，那么，损失就是当前的最大权。
那么，假设第一种情况全部成对取，剩下的都抛弃，统计完毕后通过分配中间位置来挽回一个最大的损失，这样就可以得到最优解了。

    priority_queue<long long> potential_center;//记录潜在的损失
    for (auto it = mp2.begin(); it != mp2.end(); ++it)
    {
        if ((it->second).size() >= 2 && (it->second).top() > 0)//如果是情况1或3
        {
            long long a = (it->second).top();(it->second).pop();
            long long b = (it->second).top();(it->second).pop();
            if (a + b >= 0)//情况1
            {
                ans += a + b;
                potential_center.push(-b);
            }
            else//情况3
            {
                potential_center.push(a);
            }
        }
        else if (it->second.size()>0&&it->second.top()>0)//情况2
        {
            potential_center.push(it->second.top());
        }
    }
    if(potential_center.size()>0&&potential_center.top()>0)//挽回一个损失//做一点微小的贡献
        ans += potential_center.top();

然后输出即可。

代码

惯例删了不必要的声明和定义等部分

int  main() {
    cin >> k >> n;
    while (k--)
    {
        cin >> s >> tmp;//输入
        string sr = s.reverse();
        if (sr == s)
        {
            mp2[s].push(tmp);
        }
        else//自回文串和非自回文串分开处理
        {
            if (s > sr)
            {
                mp[s].q1.push(tmp);//非自回文串存到字典序大的那个里面去
            }
            else
            {
                mp[sr].q2.push(tmp);//q1，q2是俩优先队列，分别存储这个字符串和其逆序串的信息
            }
        }
    }
    long long ans = 0;
    for (auto it = mp.begin(); it != mp.end(); ++it)//挑选可以成对的非自回文串
    {
        while (!(it->second).q1.empty() && !(it->second).q2.empty() && (it->second).q1.top() + (it->second).q2.top() > 0)
        {
            ans += (it->second).q1.top() + (it->second).q2.top();
            (it->second).q1.pop();(it->second).q2.pop();
        }
    }
    for (auto it = mp2.begin(); it != mp2.end(); ++it)//挑选必然成对的自回文串
    {
        while ((it->second).size() >= 2 && (it->second).top() > 0)
        {
            long long a = (it->second).top();(it->second).pop();
            long long b = (it->second).top();(it->second).pop();
            if (a > 0 && b > 0)
            {
                ans += a + b;
            }
            else
            {
                (it->second).push(a);(it->second).push(b);
                break;
            }
        }
    }
    priority_queue<long long> potential_center;
    for (auto it = mp2.begin(); it != mp2.end(); ++it)
    {
        if ((it->second).size() >= 2 && (it->second).top() > 0)
        {
            long long a = (it->second).top();(it->second).pop();
            long long b = (it->second).top();(it->second).pop();
            if (a + b >= 0)
            {
                ans += a + b;
                potential_center.push(-b);
            }
            else
            {
                potential_center.push(a);
            }
        }
        else if (it->second.size()>0&&it->second.top()>0)
        {
            potential_center.push(it->second.top());
        }
    }
    if(potential_center.size()>0&&potential_center.top()>0)
        ans += potential_center.top();
    cout << ans << endl;
    return 0;
}