HDU 6739 2019 ccpc秦皇岛 I. Invoker (dp + 思维）

HDU 6739

题目

有几个技能，每个技能由三个无序字符组成（要按下这三个键），给你一个字符串代表释放技能的顺序，问你最少按多少键。（技能中间连接可以抵消）

分析

两个技能字符分别是 QEE ，EEE。那么可以少按两个键，因为中间可以抵消两个 E。因此算出来最多抵消的数目，原本应该按的数目(4 * len) 减去最多抵消的数目 ans 就是最终的答案（最少按键）

每个技能有三个无序字符，也就是最多六种排列。
用 dp[i][j] 代表释放到第 i 个技能，第 i 个技能用第 j 种组合，抵消的最多按键。
转移方程就是暴力枚举当前状态与上个状态的 36 种组合取最多抵消数目。

（ 杭电 加了多组输入。

#include <bits/stdc++.h>
#define INF 0x3fffffff
#define fuck(x) cout << (x) << endl
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int dp[N][10], len;
char str[N];
string a[20][6];
map<char, int> mp;
void cal(string b, int x){
int cnt = 0;
sort(b.begin(), b.end());
do{
a[x][cnt++] = b;
} while (next_permutation(b.begin(), b.end()));
while(cnt < 6){
a[x][cnt++] = b;
}
}
void init(){
mp['Y'] = 1;
mp['V'] = 2;
mp['G'] = 3;
mp['C'] = 4;
mp['X'] = 5;
mp['Z'] = 6;
mp['T'] = 7;
mp['F'] = 8;
mp['D'] = 9;
mp['B'] = 10;
cal("QQQ", 1);
cal("QQW", 2);
cal("QQE", 3);
cal("WWW", 4);
cal("QWW", 5);
cal("WWE", 6);
cal("EEE", 7);
cal("QEE", 8);
cal("WEE", 9);
cal("QWE", 10);
}
int main(){
init();
// 预处理每种技能 6 种排列
while(~scanf("%s", str)){
len = strlen(str);
memset(dp, 0, sizeof(dp));
for (int i = 1; i < len; i++){
int x = mp[str[i]], y = mp[str[i - 1]];
if(str[i-1] == str[i]){
for(int j = 0; j < 6; j++){
dp[i][j] = dp[i-1][j] + 3;
}
}else{
for (int j = 0; j < 6; j++){
// 枚举36种组合，取最多能抵消的
for(int k = 0; k < 6; k++){
if(a[y][k][1] == a[x][j][0] && a[y][k][2] == a[x][j][1]){
dp[i][j] = max(dp[i][j], dp[i-1][k]+2);
}else if(a[y][k][2] == a[x][j][0]){
dp[i][j] = max(dp[i][j], dp[i-1][k]+1);
}else{
dp[i][j] = max(dp[i][j], dp[i-1][k]+0);
}
}
}
}
}
int ans = 0;
for(int i = 0; i < 6; i++){
// 找到最后以哪种结尾最大
ans = max(ans, dp[len - 1][i]);
}
printf("%dn", 4 * len - ans);
}
return 0;
}

最后

以上就是贪玩书本为你收集整理的HDU 6739 2019 ccpc秦皇岛 I. Invoker (dp + 思维）的全部内容，希望文章能够帮你解决HDU 6739 2019 ccpc秦皇岛 I. Invoker (dp + 思维）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。