- 回文(palindrome)
30分求调
- @ 2025-10-29 21:32:50

#include<bits/stdc++.h>
using namespace std;
int n,v[300],ch[300];
char s[1001000],t[1001000];
int ans,minn=INT_MAX;
int main(){
cin>>n;
for(int i=1;i<=26;i++){
cin>>v[i];
minn=min(minn,v[i]);
}
for(int i=1;i<=n;i++){
cin>>s[i];
t[i]=s[i];
}
for(int i=1;i<=n;i++){
ch[s[i]-'a'+1]++;
}
// for(int i=1;i<=26;i++){
// cout<<ch[i]<<' ';
// }
// cout<<endl;
for(int i=1;i<=n/2;i++){
if(s[i]==s[n-i+1]){
ch[s[i]-'a'+1]-=2;
s[i]='#',s[n-i+1]='#';
}
}
// for(int i=1;i<=26;i++){
// cout<<ch[i]<<' ';
// }
// cout<<endl;
int flag=0;
for(int i=1;i<=n;i++){
if(s[i]!='#'&&ch[s[n-i+1]-'a'+1]!=0){
// cout<<i<<' '<<n-i+1<<endl;
for(int j=i+1;j<=n;j++){
if(s[j]==s[n-i+1]){
// cout<<111;
// cout<<j<<' '<<i<<endl;
swap(t[i],t[j]);
// cout<<t[j]<<' '<<t[i]<<endl;
flag=1;
break;
}
}
}
if(flag){
flag=0;
break;
}
}
// for(int i=1;i<=26;i++){
// cout<<ch[i]<<' ';
// }
// cout<<endl;
// for(int i=1;i<=n;i++)cout<<s[i]<<' ';
// cout<<endl;
// for(int i=1;i<=n;i++)cout<<t[i]<<' ';
// cout<<endl;
// cout<<minn<<endl;
for(int i=1;i<=n;i++){
if(t[i]==t[n-i+1])continue;
// cout<<v[t[i]-'a'+1]<<' '<<v[t[n-i+1]-'a'+1]<<' '<<minn*2<<endl;
ans+=min(min((v[t[i]-'a'+1]),(v[t[n-i+1]-'a'+1])),minn);
// cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
0 comments
No comments so far...
Information
- ID
- 1611
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 9
- Tags
- (None)
- # Submissions
- 160
- Accepted
- 12
- Uploaded By