题意

翻译的很清楚了。

解法说明

记搜，正确的！

考虑将每一种字符提到开头，显然可以暴力找出所有排列情况。

因为越靠前花费越少，所以每次找到第一个要找的字符就跳出循环，将其放到开头固定，同时减去这步操作的花费。

其实也就是相当于对于字符串的每一种排列，我们都用最优的解法，即用最近的字符转移，然后看看能不能转移到这个排列，正确性显然。

记搜优化则为：遇到之前已考虑过所有排列情况的字符串（搜过的串）时直接返回之前记录的值。

举个例子

设有原字符串 ABC，且转移后的大写字母写为小写字母。

第一次转移后得到：aBC，bAC，cAB

第二次转移后得到：abC，acB，baC，bcA，caB，cbA

第三次，最后只剩一个字母就不用转移啦。

体现在代码中，每次我们保存的为大写字母（待排列）部分。

代码 AT 上跑了 106 ms，也没有很慢吧。TvT

codetime

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

string S;
int K;
map<pair<string,int>,ll>mp;

ll solve(string s,int k)
{
	int n=s.size();
	if(k<0)return 0;//剩下的步数
	if(n<=1)return 1;
	auto p=make_pair(s,k);
	if(mp[p]!=0)return mp[p];

	ll res=0;
	for(auto t:"KEY")
		for(int i=0;i<n;++i)
		{
			if(t==s[i])
			{
				res+=solve(s.substr(0,i)+s.substr(i+1),k-i);
				break;
			}
		}
	return mp[p]=res;
}

int main()
{
	cin>>S>>K;

	solve(S,K);

	cout<<mp[{S,K}]<<'\n';
	return 0;
}