Santa Claus and a Palindrome

Santa Claus and a Palindrome

题目链接：http://codeforces.com/contest/752/problem/D

贪心

很自然地，可以想到，若subS不是回文串，那么只要贪心取subS中的最大值和reverse_subS中的最大值，若他们和大于零，则加入到结果回文序列中；而当subS本身就为回文串时，需要分类讨论（可以放在结果回文序列的最中间）：

　　为了方便理解，定义：

若subS中的最大值与次大值的和小于零（或subS中只有一个值），那么称该最大值（或该值）为落单值；
若subS中最大值与次大值的和大于零，那么称该最大值与次大互为配对值。

1.取落单值中最大的值与所有配对值；

2.取所有配对值，并将其中一组配对值拆分成落单值。

最后取这两种情况的最大值即可。

代码如下：

  1 #include<iostream>
  2 #include<map>
  3 #include<queue>
  4 #include<string>
  5 #include<algorithm>
  6 #define X first
  7 #define Y second
  8 using namespace std;
  9 typedef long long ll;
 10 map<string,priority_queue<ll> >mp;
 11 map<string,priority_queue<ll> >::iterator it;
 12 ll n,k,t,ans;
 13 string s;
 14 int main(void){
 15     std::ios::sync_with_stdio(false);
 16     cin>>n>>k;
 17     for(ll i=0;i<n;++i){
 18         cin>>s>>t;
 19         mp[s].push(t);
 20     }
 21     for(it=mp.begin();it!=mp.end();++it){
 22         ll x,y;
 23         s=it->X;
 24         if(it->Y.empty())continue;
 25         reverse(s.begin(),s.end());
 26         if(s.compare(it->X)==0){
 27             while(it->Y.size()>=2){
 28                 x=it->Y.top();
 29                 it->Y.pop();
 30                 if(it->Y.top()>0){
 31                     ans+=x+it->Y.top();
 32                     it->Y.pop();
 33                 }else{
 34                     it->Y.push(x);
 35                     break;
 36                 }
 37             }
 38             continue;
 39         }
 40         if(mp[s].empty())continue;
 41         while(!it->Y.empty()&&!mp[s].empty()){
 42             x=it->Y.top();
 43             y=mp[s].top();
 44             if(x+y>0){
 45                 ans+=x+y;
 46                 it->Y.pop();
 47                 mp[s].pop();
 48             }else break;
 49         }
 50     }
 51     ll maxn=-1;
 52     for(it=mp.begin();it!=mp.end();++it){
 53         s=it->X;
 54         reverse(s.begin(),s.end());
 55         if(s.compare(it->X)==0){
 56             if(it->Y.size()>=2){
 57                 ll tmp=it->Y.top();
 58                 it->Y.pop();
 59                 if(it->Y.top()+tmp<=0){
 60                     if(tmp>maxn)maxn=tmp;
 61                 }else it->Y.push(tmp);
 62             }else if(it->Y.size()==1){
 63                 ll tmp=it->Y.top();
 64                 it->Y.pop();
 65                 if(tmp>maxn)maxn=tmp;
 66             }
 67         }
 68     }
 69     ll tt1=0,tt2=0;
 70     ll minn=1000000000000;
 71     if(maxn!=-1){
 72         tt1=maxn;
 73         for(it=mp.begin();it!=mp.end();++it){
 74             s=it->X;
 75             reverse(s.begin(),s.end());
 76             if(s.compare(it->X)==0){
 77                 if(it->Y.size()>=2){
 78                     ll t1=it->Y.top();
 79                     it->Y.pop();
 80                     ll t2=it->Y.top();
 81                     it->Y.pop();
 82                     if(t2+t1>0)tt1+=t1+t2;
 83                     it->Y.push(t1);
 84                     it->Y.push(t2);
 85                 }
 86             }
 87         }
 88     }
 89     for(it=mp.begin();it!=mp.end();++it){
 90         s=it->X;
 91         reverse(s.begin(),s.end());
 92         if(s.compare(it->X)==0){
 93             if(it->Y.size()>=2){
 94                 ll t1=it->Y.top();
 95                 it->Y.pop();
 96                 ll t2=it->Y.top();
 97                 it->Y.pop();
 98                 if(t1+t2>=0){
 99                     tt2+=t1+t2;
100                     minn=min(minn,t2);
101                 }
102             }
103         }
104     }
105     if(minn!=1000000000000)tt2-=minn;
106     cout<<ans+max(tt1,tt2)<<endl;
107 }