#include using namespace std; //Minimum Cost Flow O(FE log V) #include #include #include #include #include template struct MCF{ struct edge{ int to,rev,cap; T cost; }; vector >G; vectorh,d; vectorpv,pe; MCF(int n_=0):G(n_),h(n_,0),d(n_),pv(n_),pe(n_){} void add_edge(int from,int to,int cap,T cost) { G[from].push_back({to,(int)G[to].size(),cap,cost}); G[to].push_back({from,(int)G[from].size()-1,0,-cost}); } T min_cost_flow(int s,int t,int f)//ans or -1 { T ret=0; while(f>0) { queue >P; fill(d.begin(),d.end(),numeric_limits::max()); d[s]=0; P.push(make_pair(0,s)); while(!P.empty()) { pairp=P.front();P.pop(); if(d[p.second]0&&d[e.to]>d[p.second]+e.cost+h[p.second]-h[e.to]) { d[e.to]=d[p.second]+e.cost+h[p.second]-h[e.to]; pv[e.to]=p.second; pe[e.to]=i; P.push(make_pair(d[e.to],e.to)); } } } if(d[t]==numeric_limits::max())return 1; for(int u=0;u>N>>s; for(int i=0;i>V[i]; vector,pair > >E; int pre[4]={-1,-1,-1,-1}; int st=N,go=N+1; for(int i=N;i--;) { if(s[i]=='y') { E.push_back(make_pair(make_pair(st,i),make_pair(1,0))); if(pre[1]!=-1) { E.push_back(make_pair(make_pair(i,pre[1]),make_pair(1,-V[i]))); } pre[0]=i; } else if(s[i]=='u') { if(pre[1]!=-1) { E.push_back(make_pair(make_pair(i,pre[1]),make_pair(N,0))); } if(pre[2]!=-1) { E.push_back(make_pair(make_pair(i,pre[2]),make_pair(1,-V[i]))); } pre[1]=i; } else if(s[i]=='k') { if(pre[2]!=-1) { E.push_back(make_pair(make_pair(i,pre[2]),make_pair(N,0))); } if(pre[3]!=-1) { E.push_back(make_pair(make_pair(i,pre[3]),make_pair(1,-V[i]))); } pre[2]=i; } else { if(pre[3]!=-1) { E.push_back(make_pair(make_pair(i,pre[3]),make_pair(N,0))); } E.push_back(make_pair(make_pair(i,go),make_pair(1,-V[i]))); pre[3]=i; } } MCFP(N+2); for(pair,pair >e:E)P.add_edge(e.first.first,e.first.second,e.second.first,e.second.second); long ans=0; for(int L=1;;L++) { long T=P.min_cost_flow(st,go,1); if(T>=0)break; ans-=T; } cout<