Invoker
Time Limit: 15000/12000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 586 Accepted Submission(s): 100
Problem Description
在 dota2 中有一个叫做祈求者(Invoker)的英雄，在游戏中他有三个基础技能：冰(Quas)，雷(Wex)，火(Exort)，每施展一个技能就可以获得相应属性的一个法球(element)。
但是祈求者同时最多只能有三个法球，即如果他在有三个法球的状态下又使用了某个法球技能，那么他会获得该法球，并失去之前三个法球中最先获得的一个。
不难得出，祈求者身上的三个法球的**无顺序**组合有 10 种，每一种都对应着一个组合技能：
1. 急速冷却(Cold Snap)，无序组合 QQQ，用 Y 表示
2. 幽灵漫步(Ghost Walk)，无序组合 QQW，用 V 表示
3. 寒冰之墙(Ice Wall)，无序组合 QQE，用 G 表示
4. 电磁脉冲(EMP)，无序组合 WWW，用 C 表示
5. 强袭飓风(Tornado)，无序组合 QWW，用 X 表示
6. 灵动迅捷(Alacrity)，无序组合 WWE，用 Z 表示
7. 阳炎冲击(Sun Strike)，无序组合 EEE，用 T 表示
8. 熔炉精灵(Forge Spirit)，无序组合 QEE，用 F 表示
9. 混沌陨石(Chaos Meteor)，无序组合 WEE，用 D 表示
10. 超震声波(Deafening Blast)，无序组合 QWE，用 B 表示
当祈求者拥有三个法球的时候，使用元素祈唤(Invoke)技能，用 R 表示，便可获得当前法球组合所对应的技能，同时原有的三个法球也不会消失，先后顺序的状态也不会改变。
现在给定一个技能序列，你想按照给定的顺序将他们一个一个地祈唤出来，同时你想用最少的按键来达到目标，所以你想知道对于给定的一个技能序列，最少按多少次键才能把他们都祈唤出来。
注意：游戏开始的时候，祈求者是没有任何法球的。
Input
仅一行一个字符串 s ，表示技能序列。其中所有字母都是大写，且在 {B,C,D,F,G,T,V,X,Y,Z} 内。
1≤|s|≤105
Output
仅一行一个正整数，表示最少按键次数。
Sample Input
XDTBV
Sample Output
14
Hint
一种按键最少的方案为：QWWREERERWQRQR
Source
642ccpcQHD
OJ题号
HDU 6379
简单题意
一个人有QWE三个基础技能，和一个大招R技能，每释放一个基础技能就会获得一个相应的技能点，最多同时拥有三个技能点，最早获得的技能点会被最新释放的技能点给挤走，每次释放R技能，就会根据现有的三个技能点的组合，释放出一个特殊技能，但是释放R技能不会消耗目前拥有的技能点。技能点组合对应的特殊技能名称如上图所示。现给出一列按时间顺序释放的特殊技能，问如何释放基础QWE技能以及R技能，使得释放的技能总数最小。
正解思路
我们可以知道当前技能释放需要增加按键数，是通过是一个技能决定的，关键看上一个技能含有当前技能的QWE有几个，我们知道总共就有36种状态，我们设dp[i][j]为当前为i个技能由第j种状态得来，具体看一下代码，一看就懂。
#include<bits/stdc++.h>
using namespace std;
#define maxn 105005
#define ll long long
map<char,string>mp;
int js(char x,int l1,int r1,char y,int l2,int r2)
{int sum=0;if(mp[x][l1]==mp[y][l2]&&mp[x][l1+1]==mp[y][l2+1]&&mp[x][l1+2]==mp[y][l2+2]){return 1;}else if(mp[x][l1+1]==mp[y][l2]&&mp[x][l1+2]==mp[y][l2+1])return 2;else if(mp[x][r1]==mp[y][l2])return 3;elsereturn 4;
}
char c[maxn];
int dp[maxn][10];
int main()
{mp['Y'] = "1QQQQQQQQQQQQQQQQQQ";mp['V'] = "1QQWQWQWQQQQWQWQWQQ";mp['G'] = "1QQEQEQEQQQQEQEQEQQ";mp['C'] = "1WWWWWWWWWWWWWWWWWW";mp['X'] = "1QWWWQWWWQQWWWQWWWQ";mp['Z'] = "1WWEWEWEWWWWEWEWEWW";mp['T'] = "1EEEEEEEEEEEEEEEEEE";mp['F'] = "1QEEEQEEEQQEEEQEEEQ";mp['D'] = "1WEEEWEEEWWEEEWEEEW";mp['B'] = "1QWEQEWWEQWQEEQWEWQ";while(scanf("%s",c+1)!=EOF){int n=strlen(c+1);for(int i=1;i<=6;i++)dp[1][i]=4;for(int i=2; i<=n; i++){for(int j=1; j<=6; j++){dp[i][j]=1e9;}for(int j=1; j<=6; j++){for(int k=1; k<=6; k++){dp[i][j]=min(dp[i][j],dp[i-1][k]+js(c[i-1],(k-1)*3+1,k*3,c[i],(j-1)*3+1,j*3));}}}int ans=1e9;for(int i=1; i<=6; i++)ans=min(dp[n][i],ans);printf("%d\n",ans);}
}