字符串、搜索、贪心、广度优先搜索

贪心，每次选择能够最小化字典序的操作。如果有多种操作方式能够最小化字典序就同时扩展，若一种操作方式扩展出的结果较劣就停止扩展。使用 bfs 逐轮扩展，时间复杂度 $O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
struct Chose{int l,r;Chose(int _l,int _r):l(_l),r(_r){}};
bool on[2005][2005];
queue<Chose> q;
char s[2005];
int n,cnt;
char extend(int x){//扩展所有r-l+1=x的操作
    char ret='Z';
    vector<Chose> v;
    while(!q.empty()&&q.front().r-q.front().l+1==x) v.push_back(q.front()),q.pop();
    for(auto [l,r]:v) ret=min({ret,s[l],s[r]});
    for(auto [l,r]:v){
        if(s[l]==ret&&!on[l+1][r]) q.push(Chose(l+1,r)),on[l+1][r]=1;
        if(s[r]==ret&&!on[l][r-1]) q.push(Chose(l,r-1)),on[l][r-1]=1;
    }
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) while(!isalpha(s[i])) s[i]=getchar();
    q.push(Chose(1,n));
    for(int i=1;i<=n;i++){
        putchar(extend(n-i+1));
        if((++cnt)%80==0) putchar('\n');
    }
    return 0;
}