比赛 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;
}