| 比赛 |
2026.8.28 |
评测结果 |
WAWWWTTTTT |
| 题目名称 |
终将成为你 |
最终得分 |
10 |
| 用户昵称 |
exil |
运行时间 |
11.120 s |
| 代码语言 |
C++ |
内存使用 |
5.02 MiB |
| 提交时间 |
2026-08-28 12:43:01 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define int long long
int shu[515][515];
int s[515];
int fa[525];
int find(int x){
if(fa[x]!=x)fa[x]=find(fa[x]);
return fa[x];
}
struct node{
int l,r,sum;
};
node bian[255000];
int cnt;
bool cmp(node a,node b){
return a.sum<b.sum;
}
signed main(){
freopen("become.in","r",stdin);
freopen("become.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
string a;
cin>>a;
int e=5;
for(int i = 1;i<=n;i++){
s[i]=a[i-1]-97+1;
}
for(int i = 1;i<=n;i++){
for(int j = n;j>=1;j--){
if(i==j){
shu[i][j]=0;
}
else if(j==e){
shu[i][j]=shu[i][j+1]+1;
}
else if(j==n){
int c=0;
for(int k = i+1;k<=j;k++){
if(s[k]==s[j])c+=2;
}
shu[i][j]=c;
}
else if(j>i){
int c=0;
for(int k = i+1;k<=j;k++){
if(s[k]==s[j])c+=2;
}
if(s[i]==e){
shu[i][j]=shu[i][j+1]+1;
}
else shu[i][j]=min(c,shu[i][j+1]+1);
}
else{
shu[i][j]=shu[i][j+1]+1;
}
}
}
for(int k = 1;k<=n;k++){
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
if(i==j)continue;
shu[i][j]=min(shu[i][j],shu[i][k]+shu[k][j]);
}
}
}
for(int i = 1;i<=n;i++)fa[i]=i;
int dian=0;
for(int i = 1;i<=n;i++){
if(s[i]==e){
dian++;
for(int j = 1;j<=n;j++){
if(i==j)continue;
if(s[j]==e){
cnt++;
bian[cnt].l=i;
bian[cnt].r=j;
bian[cnt].sum=shu[i][j];
}
}
}
}
// for(int i = 1;i<=n;i++){
// for(int j = 1;j<=n;j++){
// cout<<shu[i][j]<<" ";
// }
// cout<<endl;
// }
sort(bian+1,bian+1+cnt,cmp);
int t=0;
int ans=0;
for(int i = 1;i<=cnt;i++){
int lx=find(bian[i].l),ly=find(bian[i].r);
if(lx!=ly){
t++;
ans+=bian[i].sum;
fa[lx]=ly;
}
if(t==dian-1)break;
}
cout<<ans+dian*2;
return 0;
}