题意：有Q、W、E三个按键，现在给了十种三个键的无序组合的映射技能，每个映射技能释放都需要按一下R，问将映射技能都释放出来，最少的按键次数是多少。这里会保留前面三个按键(不包括R键) 比如YY只需要按3次Q，然后一次R，释放了第一个Y，因为第二个还是Y，所以只需要在按一个R。
思路：将每个映射技能对应的按键都预处理出来。每个技能最多只有六种按键可能。 不足六种的补全和前面的一样即可。 然后用dp[i][j]表示释放了前i个技能，第i个技能用第j种按键方式的按键次数最小 容易得到转移方程就是 dp[i][j]=min( dp[i][j]，dp[i-1][k]+cal(k,j) ) 其中0<=k<6,cal(i,j)表示计算上一个技能的用第k种按键方式到当前技能用第j种按键方式需要按的次数 因为有len(s)个技能，所以肯定需要len(s)个R键，考虑先把R键次数保存即可。转移时候的cal的值的取值范围就是0，1，2，3。 最后只需要枚举释放前n种技能，最后一种技能的按键方式即可。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; char s[10][5]={"QQQ","QQW","QQE","WWW","QWW","WWE","EEE","QEE","WEE","QWE"}; char c[10][6][5]; int dp[N][10]; int mp[130]; void Init(){ for(int i=0;i<10;i++){ char S[10]; int now=0; sort(s[i],s[i]+3);///这里需要排序一下，不然比如QQE是最大字典序 next就不会在改变字符串了 memcpy(S,s[i],sizeof(s[i])); do { for(int j=0;j<3;j++) c[i][now][j]=S[j]; c[i][now][3]='\0'; ++now; }while(next_permutation(S,S+3)); while(now<6){ memcpy(c[i][now],c[i][now-1],sizeof(c[i][now-1])); ++now; } } mp['Y']=0; mp['V']=1; mp['G']=2; mp['C']=3; mp['X']=4; mp['Z']=5; mp['T']=6; mp['F']=7; mp['D']=8; mp['B']=9; } int cal(int a,int b,int x,int y){///第a种技能的第x种方式 到 第b种技能的第y种方式 if(c[a][x][0]==c[b][y][0] && c[a][x][1]==c[b][y][1] && c[a][x][2]==c[b][y][2]) return 0; if(c[a][x][1]==c[b][y][0] && c[a][x][2]==c[b][y][1]) return 1; if(c[a][x][2]==c[b][y][0]) return 2; return 3; } int main(){ Init(); string s; while(cin>>s){ int len=s.size(); int ans=len; memset(dp,0x3f,sizeof dp); for(int i=0;i<10;i++) dp[0][i]=3; for(int i=1;i<len;i++){ for(int j=0;j<6;j++){ for(int k=0;k<6;k++){ dp[i][k]=min(dp[i][k],dp[i-1][j]+cal(mp[s[i-1]],mp[s[i]],j,k)); } } } int Mi=~0u>>1; for(int i=0;i<6;i++) Mi=min(Mi,dp[len-1][i]); cout<<ans+Mi<<endl; } return 0; }