首页 > 代码库 > CodeForces - 748D Santa Claus and a Palindrome (贪心+构造)
CodeForces - 748D Santa Claus and a Palindrome (贪心+构造)
题意：给定k个长度为n的字符串，每个字符串有一个魅力值ai，在k个字符串中选取字符串组成回文串，使得组成的回文串魅力值最大。
分析：
1、若某字符串不是回文串a，但有与之对称的串b，将串a和串b所有的魅力值分别从大到小排序后，若两者之和大于0，则可以放在回文串的两边。
2、若某字符串是回文串，将其魅力值从大到小排序后，两两依次分析：(mid---可能放在回文串中间的串的最大魅力值)
(1)若两个数都是正的，那么就将其放在两边，并将结果计入ans。（ans---回文串两边的串的魅力值之和）
(2)若一正一负，且正数绝对值大，可以放在两边，也可以将正数放在中间同时舍去负数。
那么先假定这两个数是放在两边的，并将结果计入ans。
若该正数放在回文串的中间最终是mid的最大值，那么实际上结果增加了是负数的绝对值，所以将负数的绝对值与mid比较，并更新。
eg：
(i)aaa：5，-3；bbb：4;
aaa放在中间相对于放在两边最终的结果是增加了3，而bbb放在中间最终的结果是增加了4，所以aaa应当放在两边，而且中间的串应取bbb。
(ii)aaa：5，-3；bbb：2;
aaa放在中间相对于放在两边最终的结果是增加了3，而bbb放在中间最终的结果是增加了2，所以aaa放在中间是最好的情况，mid应取3。
(3)若一正一负，且负数绝对值大，那么一定不能放在两边（因为两者之和小于0），但正数可以放在中间，更新mid。
(4)若两数都是负的，那么不放进回文串。
#pragma comment(linker, "/STACK:102400000, 102400000")#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<cmath>#include<iostream>#include<sstream>#include<iterator>#include<algorithm>#include<string>#include<vector>#include<set>#include<map>#include<stack>#include<deque>#include<queue>#include<list>#define Min(a, b) ((a < b) ? a : b)#define Max(a, b) ((a < b) ? b : a)const double eps = 1e-8;inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1;}typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const int MAXN = 100000 + 10;const int MAXT = 1000000 + 10;using namespace std;map<string, int> mp;vector<int> v[MAXN];vector<string> t;int k, n;string s;int cnt;int vis[MAXN];void init(){ cnt = 0; for(int i = 0; i < MAXN; ++i) v[i].clear(); mp.clear(); memset(vis, 0, sizeof vis); t.clear();}int get_id(string x){ if(mp.count(x)) return mp[x]; return mp[x] = ++cnt;}bool judge(string x){ for(int i = 0; i < n / 2; ++i) if(x[i] != x[n - i - 1]) return false; return true;}int main(){ while(scanf("%d%d", &k, &n) == 2){ init(); for(int i = 0; i < k; ++i){ cin >> s; int id = get_id(s); int value; scanf("%d", &value); v[id].push_back(value); if(judge(s)) vis[id] = -1;//回文串 else{ t.push_back(s);//非回文串 } } int l = t.size(); for(int i = 0; i < l; ++i){ string tt = t[i]; reverse(t[i].begin(), t[i].end()); if(mp.count(t[i])){ vis[mp[tt]] = mp[t[i]]; } } int ans = 0; int mid = 0; for(int i = 1; i <= cnt; ++i){ if(!vis[i]) continue; if(vis[i] != -1){//非回文串且有对称串 vis[vis[i]] = 0; int tmp_id = vis[i]; int len = Min(v[i].size(), v[tmp_id].size()); sort(v[i].begin(), v[i].end(), greater<int>()); sort(v[tmp_id].begin(), v[tmp_id].end(), greater<int>()); for(int j = 0; j < len; ++j){ if(v[i][j] + v[tmp_id][j] > 0) ans += v[i][j] + v[tmp_id][j]; else break; } } else{ int len = v[i].size(); if(len == 1){ mid = Max(mid, v[i][0]); continue; } sort(v[i].begin(), v[i].end(), greater<int>()); for(int j = 0; j < len; j += 2){ if(j + 1 < len){ if(v[i][j] + v[i][j + 1] > 0){ ans += v[i][j] + v[i][j + 1]; if(v[i][j] >= 0 && v[i][j + 1] < 0){ mid = Max(mid, -v[i][j + 1]); } else if(v[i][j] < 0 && v[i][j + 1] >= 0){ mid = Max(mid, -v[i][j]); } } else{ if(v[i][j] >= 0){ mid = Max(mid, v[i][j]); } else if(v[i][j + 1] >= 0){ mid = Max(mid, v[i][j + 1]); } else break; } } else{ if(v[i][j] > 0) mid = Max(mid, v[i][j]); } } } } printf("%d\n", ans + mid); } return 0;}
CodeForces - 748D Santa Claus and a Palindrome (贪心+构造)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。