cf 478D.Santa Claus and a Palindrome

原来set,priority_queue也可以映射。。涨姿势2333

比较麻烦的应该就是判断自身回文的串是选2个还是选一个吧。

 #include<bits/stdc++.h>

 #define INF 0x7fffffff

 #define LL long long

 #define N 100005

 #define pill pair<int ,int >

 using namespace std;

 inline int ra()

 {

     int x=,f=; char ch=getchar();

     while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

     while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

     return x*f;

 }

 struct Node{

     int val;

     string s;

 }node[N];

 map<string, multiset<int > > dic;

 LL ans;

 int n,k,m;

 bool cmp(Node a, Node b)

 {

     return a.val>b.val;

 }

 int main()

 {

     n=ra(); m=ra();

     for (int i=; i<n; i++)

     {

         cin>>node[i].s>>node[i].val;

         dic[node[i].s].insert(node[i].val);

     }

     int k=,x=,tmp=;

     for (int i=; i<n; i++)

     {

         string s1=node[i].s;

         if (dic[s1].size()==) continue;

         int val=(*dic[s1].rbegin());

         if (val<) continue;

         reverse(s1.begin(),s1.end());

         dic[node[i].s].erase(dic[node[i].s].find(val));

         if (dic[s1].size()!=)

         {

             tmp=(*dic[s1].rbegin());

             dic[s1].erase(dic[s1].find(tmp));

             if (val+tmp>=)

             {

                 ans+=val+tmp;

                 if (s1==node[i].s)

                     x=max(-tmp,x);

             }

             else if (s1==node[i].s)

                 x=max(x,val);

         }

         else if (s1==node[i].s) x=max(val,x);

     }

     cout<<ans+x;

     return ;

 }