2019-CCPC-秦皇岛站-Problem I. Invoker（DP）

题意：

一个人有QWE三个基础技能，和一个大招R技能，每释放一个基础技能就会获得一个相应的技能点，最多同时拥有三个技能点，最早获得的技能点会被最新释放的技能点给挤走，每次释放R技能，就会根据现有的三个技能点的组合，释放出一个特殊技能，但是释放R技能不会消耗目前拥有的技能点。技能点组合对应的特殊技能名称如上图所示。现给出一列按时间顺序释放的特殊技能，问如何释放基础QWE技能以及R技能，使得释放的技能总数最小。

解题思路：

由于每一次释放技能是和前一次释放的技能顺序有关联，由此可以想到递推，由上一次的状态推算本次的状态，也就是DP。至于状态转移，如果前一次释放R技能时，后两个技能点和本次需要的前两个技能点相同，那么本次只需要释放一个额外的技能加上R技能就可以获得特殊技能了。如果只有前一次的最后一个技能和本次的第一个技能相同，那么就需要两个特殊的技能。为了简化代码，可以直接暴力枚举前一次和本次的三个技能组合，计算额外需要释放的技能。进一步简化的话可以发现，如果有连续的相同的特殊技能，例如XXVV那么其实只需要存XV就行了，因为相同的特殊技能，只要多释放一次R技能就可以获得了。由于基础技能只有三个，最多的组合数也就是6个，因此数组需要需要开二维的DP[N][6]的数组。有了以上的分析，代码就很容易写出来了。

代码：

#include <bits/stdc++.h>

const int N = 1e6+100;

using namespace std;
int s[N];              // 存放特殊技能序列
char dic[10][6][4] = { // 十个特殊技能的各自的6种组合，少于6种的也给他补全
 {"QQQ","QQQ","QQQ","QQQ","QQQ","QQQ"},
 {"QQW","QWQ","WQQ","WQQ","WQQ","WQQ"},
 {"QQE","QEQ","EQQ","EQQ","EQQ","EQQ"},
 {"WWW","WWW","WWW","WWW","WWW","WWW"},
 {"QWW","WQW","WWQ","WWQ","WWQ","WWQ"},
 {"WWE","WEW","EWW","EWW","EWW","EWW"},
 {"EEE","EEE","EEE","EEE","EEE","EEE"},
 {"QEE","EQE","EEQ","EEQ","EEQ","EEQ"},
 {"WEE","EWE","EEW","EEW","EEW","EEW"},
 {"QWE","QEW","EQW","EWQ","WEQ","WQE"},
};
map<char,int> mp;   // map存每个特殊技能对应的编号，方便代码编写
int dp[N][6];       // dp数组

int dif(int a,int b,int pos1,int pos2)   // 计算本次技能组合相对于上一次，需要释放多少个额外的技能
{
    if (dic[a][pos1][1] == dic[b][pos2][0] && dic[a][pos1][2] == dic[b][pos2][1])
        return 1;
    if (dic[a][pos1][2] == dic[b][pos2][0])
        return 2;
    return 3;
}

int main()
{
    char tmp;
    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 ans = 0;
    int pos = 0;
    tmp = getchar();
    while(tmp != '\n')
    {
    	// 去掉连续重复的技能序列
        if(pos >= 1 && mp[tmp] == s[pos-1])
            ans ++;
        else
            s[pos++] = mp[tmp];
        tmp = getchar();
    }
    // 初始化dp数组
    for(int i = 1;i < pos ; i ++)
        for(int j = 0 ; j < 6 ; j ++)
            dp[i][j] = 10*N;
    // 每一个特殊技能都需要一个R技能的释放，所以在这直接加上特殊技能序列的长度就行
    ans += pos;
    dp[0][0] = 3; dp[0][1] = 3; dp[0][2] = 3; dp[0][3] = 3; dp[0][4] = 3; dp[0][5] = 3;
    // 递推求解
    for(int i = 1;i < pos ; 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] + dif(s[i-1],s[i],k,j));
    }
    // 选取最优解
    int mi = dp[pos-1][0];
    for(int k = 0 ; k < 6 ; k ++)
        mi = min(dp[pos-1][k],mi);
    cout<<mi+ans<<endl;
    return 0;
}