题目链接


首先，根据数字，大写字母，小写字母的情况，我们可以先按照6种情况来分类讨论。

那么，这个题跟51nod 1241看起来很像了：要求最少的整理次数，即求有多少个可以连续的：但是这个题的数字是可以重复的

所以，我们需要先对其进行整理，数字按照从小到大排序，字母也一样


然后求原串和构造出来的新串的匹配数就好

参考题解：

writeup


代码如下：

#include<bits/stdc++.h>
using namespace std;

const int maxn=20;
int dp[maxn][maxn];
int digit,big,small,T,ans;
char D[maxn],B[maxn],S[maxn],a[maxn];
string Digit,Big,Small,SA;

void solve(){
    int Tmp=0;
    memset(dp,0,sizeof(dp));
    for(int i=0;i<13;i++)
        for(int j=0;j<13;j++){
            if (a[i]==SA[j]){
            	if (i==0||j==0) dp[i][j]=1;
            	else dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
            	if (i==0) dp[i][j]=0;
            	else dp[i][j]=dp[i-1][j];
            }
            Tmp=max(Tmp,dp[i][j]);
        }
    ans=min(ans,13-Tmp);
}

void change(char x[],int len){
    for(int i=0;i<len;i++)
        for(int j=i+1;j<len;j++)
            if (x[i]>x[j]) swap(x[i],x[j]);
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",a);
        //printf("%s\n",a);
        digit=big=small=0;
        ans=13;
        for(int i=0;i<13;i++){
            if (a[i]>='0'&&a[i]<='9') D[digit++]=a[i];
            else if (a[i]>='a'&&a[i]<='z') S[small++]=a[i];
            else B[big++]=a[i];
        }
        change(D,digit);
        change(S,small);
        change(B,big);
        Digit=Small=Big="";
        for(int i=0;i<digit;i++) Digit+=D[i];
        for(int i=0;i<small;i++) Small+=S[i];
        for(int i=0;i<big;i++) Big+=B[i];
        //cout<<Digit<<Small<<Big<<endl;
        SA=Digit+Small+Big;//cout<<SA<<endl;
        solve();
        SA=Digit+Big+Small;//cout<<SA<<endl;
        solve();
        SA=Big+Digit+Small;//cout<<SA<<endl;
        solve();
        SA=Big+Small+Digit;//cout<<SA<<endl;
        solve();
        SA=Small+Digit+Big;//cout<<SA<<endl;
        solve();
        SA=Small+Big+Digit;//cout<<SA<<endl;
        solve();
        printf("%d\n",ans);
    }
    return 0;
}