Santa Claus and a Palindrome
2024-09-15 07:34:27
Santa Claus and a Palindrome
题目链接：http://codeforces.com/contest/752/problem/D
贪心
很自然地，可以想到，若subS不是回文串，那么只要贪心取subS中的最大值和reverse_subS中的最大值，若他们和大于零，则加入到结果回文序列中；而当subS本身就为回文串时，需要分类讨论（可以放在结果回文序列的最中间）：
为了方便理解，定义：
- 若subS中的最大值与次大值的和小于零（或subS中只有一个值），那么称该最大值（或该值）为落单值；
- 若subS中最大值与次大值的和大于零，那么称该最大值与次大互为配对值。
1.取落单值中最大的值与所有配对值；
2.取所有配对值，并将其中一组配对值拆分成落单值。
最后取这两种情况的最大值即可。
代码如下：
#include<iostream>
#include<map>
#include<queue>
#include<string>
#include<algorithm>
#define X first
#define Y second
using namespace std;
typedef long long ll;
map<string,priority_queue<ll> >mp;
map<string,priority_queue<ll> >::iterator it;
ll n,k,t,ans;
string s;
int main(void){
std::ios::sync_with_stdio(false);
cin>>n>>k;
for(ll i=;i<n;++i){
cin>>s>>t;
mp[s].push(t);
}
for(it=mp.begin();it!=mp.end();++it){
ll x,y;
s=it->X;
if(it->Y.empty())continue;
reverse(s.begin(),s.end());
if(s.compare(it->X)==){
while(it->Y.size()>=){
x=it->Y.top();
it->Y.pop();
if(it->Y.top()>){
ans+=x+it->Y.top();
it->Y.pop();
}else{
it->Y.push(x);
break;
}
}
continue;
}
if(mp[s].empty())continue;
while(!it->Y.empty()&&!mp[s].empty()){
x=it->Y.top();
y=mp[s].top();
if(x+y>){
ans+=x+y;
it->Y.pop();
mp[s].pop();
}else break;
}
}
ll maxn=-;
for(it=mp.begin();it!=mp.end();++it){
s=it->X;
reverse(s.begin(),s.end());
if(s.compare(it->X)==){
if(it->Y.size()>=){
ll tmp=it->Y.top();
it->Y.pop();
if(it->Y.top()+tmp<=){
if(tmp>maxn)maxn=tmp;
}else it->Y.push(tmp);
}else if(it->Y.size()==){
ll tmp=it->Y.top();
it->Y.pop();
if(tmp>maxn)maxn=tmp;
}
}
}
ll tt1=,tt2=;
ll minn=;
if(maxn!=-){
tt1=maxn;
for(it=mp.begin();it!=mp.end();++it){
s=it->X;
reverse(s.begin(),s.end());
if(s.compare(it->X)==){
if(it->Y.size()>=){
ll t1=it->Y.top();
it->Y.pop();
ll t2=it->Y.top();
it->Y.pop();
if(t2+t1>)tt1+=t1+t2;
it->Y.push(t1);
it->Y.push(t2);
}
}
}
}
for(it=mp.begin();it!=mp.end();++it){
s=it->X;
reverse(s.begin(),s.end());
if(s.compare(it->X)==){
if(it->Y.size()>=){
ll t1=it->Y.top();
it->Y.pop();
ll t2=it->Y.top();
it->Y.pop();
if(t1+t2>=){
tt2+=t1+t2;
minn=min(minn,t2);
}
}
}
}
if(minn!=)tt2-=minn;
cout<<ans+max(tt1,tt2)<<endl;
}
最新文章
- ViewController respondsToSelector 错误的解决方法
- ListView控件--2016年12月9日
- Dynamic range compression
- Linux 通配符
- C++11 智能指针unique_ptr使用 -- 以排序二叉树为例
- c# 常用正则
- git 10.8
- String对象的Replace()
- VS2015创建类库项目后添加不了WPF资源字典，窗口，用户控件处理办法
- cacti监控服务器
- [Python] 02 - String
- NetBeans 插件开发简介
- THE TOOLS TO MANAGE YOUR DATA ACROSS CLOUDS
- 菜鸟学Java（三）——JSTL标签之核心标签
- 为什么学Python语言，只需四步全面了解Python语言
- 关于SizeOf、Length
- 为什么用strlcpy取代strncpy
- 原创 gif png bmp jeg 显示方法
- svn密码 在服务端 到底是明文保存，还是密文保存
- IOS Post请求（请求服务器）