这题的思维难度不是很大,属于编程实现细节处理较多的题。
暂且把每个字符串的“beauty”称为魅力值,用一个优先队列数组将同一个字符串的所有魅力值保存,通过map将不同字符串编号,就可以十分方便的查询到每个字符按串对应的魅力值队列了。之所以使用优先队列,是因为先处理魅力值更大的才能使得最后的回文串魅力值的和最大。
每个字符串氛围回文串和非回文串,应该分开考虑。
1.先处理非回文字符串,非回文字符串必须把它本身和它的对称串同时处理,因为两个才能对称嘛。
首先取两个字符串队首的魅力值:
int m=q[h].top(); q[h].pop(); int n=q[f].top(); q[f].pop();
对于m和n,当m<0,直接退出;
如果m+n<=0 直接退出;
如果m+n>0 加入最后的答案即可.
2.然后处理较为复杂的回文串。特别注意,回文串可以单独放置一个,因为它自身就是对称的。
1.如果回文串队列中只剩余1个字符串,即q[h].size()==1
如果小于等于0,直接退出;
如果大于零,不能直接退出,因为它可能最后被选中作为单独放置。当然,最后可能会出现多个可能单独放置的回文串,显而易见应该选择魅力值最大的回文串。因此直接用一个变量把最大值保存即可。
2.如果回文串队列中,剩余多个字符串时,取队首前两个元素:
int m=q[h].top(); q[h].pop(); int n=q[h].top(); q[h].pop();
如果m<=0,直接退出;
如果m>0&&n>=0,则将m+n加入最后答案;
如果m>0&&n<0,若m+n>0,此时m、n面临两种选择,要么直接选择m和n直接加入最后答案,或择将m作为单独放置。当然此时无法做出最佳选择,应该加入另外一个结构体数组中,结构体中存储两个元素m和n;若m+n<=0直接将m与此时最大单独放置的值进行比较,取较大值,之所以能直接作为单独放置的选择,是因为m+n<0对最后的答案没有帮助,如果只选择m可能会有帮助。
3.最后一步就是处理单独的放置最大值,以及结构体数组:
因为一定要选择一个单独放置的回文串,那么就枚举结构体数组,如果结构体数组中某个元素的m作为单独放置之后,其他元素一定会全部取m+n,因为要使得最后的魅力值之和最大,也可能是去原先单独放置的最大值,同时把结构体中所有元素都取m+n。
我想可能很多地方都没有讲清楚,大家对这题有什么问题欢迎提出。
AC代码:
#include<cstdio> #include<map> #include<queue> #include<vector> #include<string> #include<iostream> #include<algorithm> using namespace std; const int maxn=1e5+5; struct node{ int a,b; node(){} node(int a,int b):a(a),b(b){ } }w[maxn]; string str[maxn]; string rever(string p){ string s=""; for(int i=p.size()-1;i>=0;--i){ s+=p[i]; } return s; } bool is_pal(string p){ int x=0,y=p.size()-1; while(x<y){ if(p[x]!=p[y]) return false; x++; y--; } return true; } map<string,int>ha1,ha2; priority_queue<int>q[maxn]; vector<node>pal; int main(){ int k,n; while(scanf("%d%d",&k,&n)!=EOF){ int big=0; //最大选择 string a; int b; int x=-1; for(int i=0;i<k;++i){ cin>>a>>b; str[i]=a; int ind; if(!ha2.count(a)) { ++x; ind=x; ha2[a]=x; } else ind=ha2[a]; q[ind].push(b); } int ans=0; for(int i=0;i<k;++i){ if(ha1[str[i]]==1) continue; ha1[str[i]]=ha1[rever(str[i])]=1; int h=ha2[str[i]]; if(is_pal(str[i])){ if(q[h].empty()||q[h].top()<=0) continue; while(!q[h].empty()&&q[h].top()>0){ if(q[h].size()==1){ if(q[h].top()>0) big=max(big,q[h].top()); q[h].pop(); } else { int m=q[h].top(); q[h].pop(); int n=q[h].top(); q[h].pop(); if(m>0){ if(n<0) { if(m+n>0) pal.push_back(node(m,n)); else big=max(big,m); } else if(n>=0) ans+=m+n; } } } } else{ if(q[h].empty()) continue; string s=rever(str[i]); if(!ha2.count(s)) continue; //找不到对称串 int f=ha2[s]; while(!q[h].empty()&&!q[f].empty()){ int m=q[h].top(); q[h].pop(); int n=q[f].top(); q[f].pop(); if(m+n<=0) break; else if(m+n>0) ans+=m+n; } } } int sum=0; for(int i=0;i<pal.size();++i){ sum+=pal[i].a+pal[i].b; } int u=sum+big; for(int i=0;i<pal.size();++i){ if(pal[i].a>big) u=max(u,sum-pal[i].b); } ans+=u; printf("%d\n",ans); } return 0; }
如有不当之处欢迎指出!