题意：
连续3个特定的按键（在这3个中不要求顺序）能使出某个技能，使出不同技能所需要的按键可以重叠，给你一个技能序列，问你最少花费多少次按键能按顺序使出这些招数。
题解：
dp，dp[i][j]代表使出第i个技能后，最后3个按键组合是j的最少需要按键数，暴力枚举即可。
思路比较绕，实际码的时候很自闭。
#include<bits/stdc++.h> using namespace std; #define MAXN 100000+50 char s[MAXN]; string jineng[15][6]={ {"QQQ","QQQ","QQQ","QQQ","QQQ","QQQ"}, {"QQW","QQW","QWQ","QWQ","WQQ","WQQ"}, {"QQE","QQE","QEQ","QEQ","EQQ","EQQ"}, {"WWW","WWW","WWW","WWW","WWW","WWW"}, {"QWW","QWW","WQW","WQW","WWQ","WWQ"}, {"WWE","WWE","WEW","WEW","EWW","EWW"}, {"EEE","EEE","EEE","EEE","EEE","EEE"}, {"QEE","QEE","EQE","EQE","EEQ","EEQ"}, {"WEE","WEE","EEW","EEW","EWE","EWE"}, {"QWE","QEW","WEQ","WQE","EWQ","EQW"} }; //CXZTFDB int num[500]; int dp[MAXN][6]; int get_dif(int id1,int id2,int pos1,int pos2) { if(jineng[id1][pos1][0]==jineng[id2][pos2][0]&&jineng[id1][pos1][1]==jineng[id2][pos2][1] &&jineng[id1][pos1][2]==jineng[id2][pos2][2]) return 0; if(jineng[id1][pos1][1]==jineng[id2][pos2][0]&&jineng[id1][pos1][2]==jineng[id2][pos2][1]) return 1; if(jineng[id1][pos1][2]==jineng[id2][pos2][0]) return 2; return 3; } int main() { int ans; scanf("%s",s); int len=strlen(s); ans=len*3; memset(num,0,sizeof(num)); num['Y']=0,num['V']=1,num['G']=2,num['C']=3, num['X']=4,num['Z']=5,num['T']=6,num['F']=7, num['D']=8,num['B']=9; for(int i=0;i<len;++i) for(int j=0;j<6;++j) dp[i][j]=len*3; for(int i=0;i<6;++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][j]=min(dp[i][j],dp[i-1][k]+get_dif(num[s[i-1]],num[s[i]],k,j)); } for(int i=0;i<6;++i) ans=min(ans,dp[len-1][i]); cout<<ans+len<<endl; }