文件详细信息

下载本文件

本文件的大小为 2939 字节。

#include<algorithm>
#include<cstdio>
#include<cstring>
namespace IO{
	const int ARR_SIZE=1<<15;
	char input[ARR_SIZE],*si=input,*ti=input;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	template<typename T>
	void read(T&num){
		int ch=gc();
		num=0;
		while(ch<48||ch>57)ch=gc();
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
	}
	void getstr(char*s){
		char ch=gc();
		while(ch==' '||ch=='\r'||ch=='\n'||ch=='\t')ch=gc();
		while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!='\t'&&ch!=EOF)*(s++)=ch,ch=gc();
		*s='\0';
	}
}
using IO::read;
using IO::getstr;
const int maxn=100,inf=0x3f3f3f3f,ninf=0xc0c0c0c0;
int n,half;
char s[maxn+2];
int v[maxn+1];
template<const int maxnode,const int maxedge>
struct FlowGraph{
	int node,S,T;
	int head[maxnode+1],total=1,cur[maxnode+1];
	struct Edge{
		int to,next,flow,cost;
	}e[maxedge*2+2];
	void add(const int u,const int v,const int w1,const int c1){
		e[++total]=Edge{v,head[u],w1,c1};
		head[u]=total;
		e[++total]=Edge{u,head[v],0,-c1};
		head[v]=total;
	}
	bool vis[maxnode+1];
	int dis[maxnode+1],q[maxnode+5],qlen,front,tail;
	inline int qmod(const int x){
		return x+((x>>31)&qlen);
	}
	bool spfa(){
		memset(dis+1,0xc0,sizeof(int)*node);
		front=1,tail=0;
		q[tail=qmod(tail+1-qlen)]=S;
		vis[S]=true;
		dis[S]=0;
		while(qmod(front-1)!=tail){
			const int u=q[front];
			front=qmod(front+1-qlen);
			vis[u]=false;
			for(int i=head[u];i;i=e[i].next){
				const int v=e[i].to;
				if(e[i].flow&&dis[v]<dis[u]+e[i].cost){
					dis[v]=dis[u]+e[i].cost;
					if(!vis[v]){
						vis[v]=true;
						q[tail=qmod(tail+1-qlen)]=v;
					}
				}
			}
		}
		return dis[T]!=ninf;
	}
	int dfs(const int u,int in){
		if(u==T)return in;
		vis[u]=true;
		int out=0;
		for(int&i=cur[u];i;i=e[i].next){
			const int v=e[i].to;
			if(e[i].flow&&dis[v]==dis[u]+e[i].cost&&!vis[v]){
				const int res=dfs(v,in<e[i].flow?in:e[i].flow);
				in-=res;
				out+=res;
				e[i].flow-=res;
				e[i^1].flow+=res;
				if(!in)break;
			}
		}
		if(!out)dis[u]=ninf;
		vis[u]=false;
		return out;
	}
	int dinic(){
		int maxcost=0;
		while(spfa()){
			memcpy(cur+1,head+1,sizeof(int)*node);
			maxcost+=dfs(S,inf)*dis[T];
		}
		return maxcost;
	}
};
FlowGraph<maxn+28,(maxn>>1)*(26+1)+26>G;
int cnt[26];
int main(){
	read(n),half=n>>1;
	G.node=half+26+2,G.S=G.node-1,G.T=G.node,G.qlen=G.node+2;
	getstr(s+1);
	for(int i=1;i<=n;i++)cnt[s[i]-'a']++;
	for(int i=1;i<=n;i++)read(v[i]);
	for(int ch=0;ch<26;ch++)
		if(cnt[ch])
			G.add(G.S,half+ch+1,cnt[ch],0);
	for(int i=1;i<=half;i++)G.add(i,G.T,2,0);
	for(int i=1;i<=half;i++)
		for(int ch=0;ch<26;ch++){
			if(s[i]==(ch+'a')){
				if(s[n-i+1]==(ch+'a'))G.add(half+ch+1,i,1,std::max(v[i],v[n-i+1]));
				else G.add(half+ch+1,i,1,v[i]);
			}else{
				if(s[n-i+1]==(ch+'a'))G.add(half+ch+1,i,1,v[n-i+1]);
				else G.add(half+ch+1,i,1,0);
			}
		}
	printf("%d\n",G.dinic());
	return 0;
}