abc227e

E - Swap
首先我们注意到，加入我们想要一个串T，那么最小步数是唯一的。
设\(f[i][j][e][y]\)表示当前到第i个字符，一共用掉了j次，前面有e个E，y个Y。
然后转移即可，因为k不会大于\(n^2\)，预处理第x个字符的位置即可。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#include<cmath>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
const int N=30+5;
const int M=1000;
ll f[N][M][N][N];
int n,tot,x,pos,z;
char s[N];
int a[N],t[N][4],p[N][4],k;
int main() {
   
//    #ifdef  LOCAL
//        freopen("data.in","r",stdin);
//        freopen("out.txt","w",stdout);
//    #endif

    scanf("%s",s+1);
    n=strlen(s+1);
    fo(i,1,n) {
        if (s[i]=='K') a[i]=0;
        if (s[i]=='E') a[i]=1;
        if (s[i]=='Y') a[i]=2;
    }

    scanf("%d",&tot);
    tot=min(tot,n*(n-1)/2);

    fo(i,1,n) {
        fo(j,0,2) t[i][j]=t[i-1][j];
        t[i][a[i]]++;

        p[t[i][a[i]]][a[i]]=i;
    }

    f[0][0][0][0]=1;
    fo(i,0,n-1) {
        fo(j,0,tot) {
            fo(e,0,min(i,t[n][1])) fo(y,0,min(i-e,t[n][2])) {
                k=i-e-y;
                if (k<0 || k>t[n][0]) continue;

                if (k+1<=t[n][0])  { // k
                    pos=p[k+1][0];
                    z=max(0,t[pos][1]-e)+max(0,t[pos][2]-y);
                    if (z+j<=tot) f[i+1][z+j][e][y]+=f[i][j][e][y];
                }

                if (e+1<=t[n][1]) { //e 
                    pos=p[e+1][1];
                    z=max(0,t[pos][0]-k)+max(0,t[pos][2]-y);
	                if (z+j<=tot) f[i+1][z+j][e+1][y]+=f[i][j][e][y];
                }
                
           		if (y+1<=t[n][2]) { //y 
                    pos=p[y+1][2];
                    z=max(0,t[pos][0]-k)+max(0,t[pos][1]-e);
                    if (z+j<=tot) f[i+1][z+j][e][y+1]+=f[i][j][e][y];
                }
            }
        }
    }

    

    ll ans=0;
    fo(i,0,tot) ans+=f[n][i][t[n][1]][t[n][2]];
    
    printf("%lld",ans);

    return 0;
}