  /**//*
 题意: 对一个字符串允许最多k的翻转，每次翻转该串的前缀，且前缀必须大于上一次的
求使之字典序最小
dp[k,i] 表示对前i个字符串翻转k次（第k次就翻转前i个了）得到的最小值
转移就是枚举上一次翻转的位置了
dp[k,i] = min{ rev(_dp[k-1,j] + str[j+1 i]) } = min{ rev(str[j+1i]) + rev(_dp[k-1,j]) }
这里的_dp[]
一开始我以为_dp[]就是最大的，然后翻转后就是最小的
对于字符串，最大翻转后不一定是最小的！！
如 EB , CB 翻转后是BE , BC
其实看上面，最终还是要使得串[1j]翻转后最小，那就用rdp[k-1,j]表示对前j个翻转了k-1次后再翻转一次后最小
（其实也就是第k-1次没翻转） rdp[k-1,j] = rev(_dp[k-1,j])
所以dp[k,i] = min{ rev(str[j+1i]) + rdp[k-1,j]}
而 rdp[k,i] = min{ dp[k-1,j] + str[j+1i] } 最后的不用翻转
需要优化
 */
 #include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN = 110;
string dp[2][MAXN],rdp[2][MAXN];
int main()
{
int T,N,K,t=1;
string str,ans;
for(cin>>T;T--;)
  {
cin>>N>>K;
cin>>str;
ans = str;
int pre = 0,now = 1;
for(int i = 0; i <= N; i++)//dp[0,0] = rdp[0,0] = ""
{
string sub = str.substr(0, i);
dp[pre][i] = sub;
reverse(sub.begin(),sub.end());
rdp[pre][i] = sub;
 }
//[k,i-1] = rev(j+1,i-1) + [k-1,j] k-1<=j<=i-2
//[k,i] = rev(j+1,i) + [k-1,j] k-1<=j<=i-1
// = i + [k-1,i-1] , rev(j+1,i) + [k-1,j] k-1<=j<i-1
// = i + [k-1,i-1] , i + rev(j+1,i-1) + [k-1,j] k-1<=j<=i-2
// = i + [k-1,i-1] , i + [k,i-1]
// [k,i] <- [k-1,i-1]
// [k,i] <- [k,i-1]
for(int k = 1; k <= K; k++)
{
for( int i = k ; i<=N ; i++ )
{
dp[now][i] = str[i-1] + rdp[pre][i-1];
if(i!=k)dp[now][i] = min(dp[now][i] , str[i-1] + dp[now][i-1]);
rdp[now][i] = dp[pre][i-1] + str[i-1];
if(i!=k)rdp[now][i] = min(rdp[now][i] , rdp[now][i-1] + str[i-1]);
ans = min(ans,dp[now][i] + str.substr(i,N-i));
}
swap(now,pre);
}
cout<<"Case "<<t++<<": "<<ans<<endl;
}
return 0;
}
|