[数据结构与算法]Invoker(预处理+dp)

Invoker

[Link](Problem - 6739 (hdu.edu.cn))

题意

你有三个小技能，每使用一个小技能就会给你的卡槽留下一个相应的标记，卡槽最多有三个标记，当有一个新的标记到来且没有位置时最先到的标记被移除，依次顺移。卡槽内三个标记不同的无序组合可以放出不同的大招，当有三个标记后就可以放大招啦。现在给你一个大招序列，问你最少用多少次操作可以把这个大招序列发出去。

题解

首先发现每一个大招就确定了三个无序的标记，它是不符合局部贪心到整体最优的。但是假设当前到了第i位，那么从开始到第i位的所有操作，是有一个最优解的且和后面的操作无关。因此想到的dp，那么怎么考虑设计维度可以补充不漏的把状态表示出来呢？首先假设当前到了第i位，那么第i-1位时什么情况下他是最优的呢，这个是无法直接判断了因此我们要加一维来表示前一个大招的标记情况。我们假设
$f[i,j]表示到第i个大招且是第j种标记情况的最小操作次数$
然后就可以直接暴力转移了。

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
int a[N];
char dic[10][6][4] {
    {"QQQ","QQQ","QQQ","QQQ","QQQ","QQQ"},
    {"QQW","QWQ","WQQ","QQW","QWQ","WQQ"},
    {"QQE","QEQ","EQQ","QQE","QEQ","EQQ"},
    {"WWW","WWW","WWW","WWW","WWW","WWW"},
    {"QWW","WQW","WWQ","QWW","WQW","WWQ"},
    {"WWE","WEW","EWW","WWE","WEW","EWW"},
    {"EEE","EEE","EEE","EEE","EEE","EEE"},
    {"QEE","EQE","EEQ","QEE","EQE","EEQ"},
    {"WEE","EWE","EEW","WEE","EWE","EEW"},
    {"QWE","QEW","WQE","WEQ","EWQ","EQW"},
};
map<char, int> mp;
int s[N];
string str;
int f[N][6];
int get(int v1, int v2, int p1, int p2) {
    if (dic[v1][p1][0] == dic[v2][p2][0] && dic[v1][p1][1] == dic[v2][p2][1] && dic[v1][p1][2] == dic[v2][p2][2])   return 0;
    if (dic[v1][p1][1] == dic[v2][p2][0] && dic[v1][p1][2] == dic[v2][p2][1]) return 1;
    if (dic[v1][p1][2] == dic[v2][p2][0])   return 2;
    return 3;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    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;
    while(cin >> str) {
        int res = 0, cnt = 0;
        for (int i = 0; i < str.size(); i ++ ) s[i + 1] = mp[str[i]];
        memset(f, 0x3f, sizeof f);
        for (int i = 0; i < 6; i ++ ) f[1][i] = 3;
        for (int i = 2; i <= str.size(); i ++ )
            for (int j = 0; j < 6; j ++ )
                for (int k = 0; k < 6; k ++ )   
                    f[i][j] = min(f[i][j], f[i - 1][k] + get(s[i-1], s[i], k, j));
        int mn = INF;
        for (int i = 0; i < 6; i ++ )   mn = min(mn, f[str.size()][i]);
        cout << mn + str.size()  << endl;
    }
    return 0;
}