2019ICPC秦皇岛I Invoker

2024-09-04 23:08
文章标签 invoker 秦皇岛 2019icpc

本文主要是介绍2019ICPC秦皇岛I Invoker,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

 

题意:一个英雄四个基础技能QWER,QWE一共有十种组合对应十个技能R是释放该技能(该英雄会保存着三个法球当你有新的一个法球的时候最先生成的那一个法球就会消失),求给你一个技能序列求你怎么搓才能在最少的按键情况下把这些技能搓出来,每个技能搓出来是无序的注意这里是无序的也就是说只要有对应数目的字符就能把这个技能放出来所以这个技能能放出来最多有6种序列。这样把每个技能对应的所有搓招顺序放在数组里存好到时候直接取就行然后直接暴力循环就行了。

 

#include <bits/stdc++.h>
using namespace std;
char dis[10][6][4]{
{{"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"},{"WWQ"},{"WQW"},{"WQW"},{"WQW"},{"WQW"}},
{{"WWE"},{"WEW"},{"EWW"},{"EWW"},{"EWW"},{"EWW"}},
{{"EEE"},{"EEE"},{"EEE"},{"EEE"},{"EEE"},{"EEE"}},
{{"QEE"},{"EEQ"},{"EQE"},{"EQE"},{"EQE"},{"EQE"}},
{{"WEE"},{"EEW"},{"EWE"},{"EWE"},{"EWE"},{"EWE"}},
{{"QWE"},{"WEQ"},{"EQW"},{"EWQ"},{"WQE"},{"QEW"}}
};
int dp[1000000][6];
map<char,int>ch;
int dii(int x,int y,int z,int q){if(dis[x][z][1]==dis[y][q][0]&&dis[x][z][2]==dis[y][q][1])return 1;else if(dis[x][z][2]==dis[y][q][0])return 2;return 3;
}
char c[1000000],d[1000000];
int main(){ch['Y']=0,ch['V']=1,ch['G']=2,ch['C']=3,ch['X']=4,ch['Z']=5,ch['T']=6,ch['F']=7,ch['D']=8,ch['B']=9;while(~scanf("%s",c)){int ans=0,cnt=0;ans=strlen(c);d[++cnt]=c[0];for(int i=1;i<strlen(c);i++){if(c[i]!=c[i-1])d[++cnt]=c[i];}memset(dp,0x3f3f3f3f,sizeof(dp));dp[1][0]=3,dp[1][1]=3,dp[1][2]=3,dp[1][3]=3,dp[1][4]=3,dp[1][5]=3;for(int i=2;i<=cnt;i++){for(int j=0;j<6;j++)for(int k=0;k<6;k++){dp[i][k]=min(dp[i][k],dp[i-1][j]+dii(ch[d[i-1]],ch[d[i]],j,k));}}int maxx=0x3f3f3f3f;for(int i=0;i<6;i++){maxx=min(maxx,dp[cnt][i]);}cout<<maxx+ans<<endl;}
}

 

这篇关于2019ICPC秦皇岛I Invoker的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137291

相关文章

2023 CCPC(秦皇岛)现场(第二届环球杯.第 2 阶段:秦皇岛)部分题解

所有题目链接:Dashboard - The 2023 CCPC (Qinhuangdao) Onsite (The 2nd Universal Cup. Stage 9: Qinhuangdao) - Codeforces 中文题面: contest-37054-zh.pdf (codeforces.com) G. Path 链接: Problem - G - Codeforces

第九届中国大学生程序设计竞赛(秦皇岛)-(CCPC2023-Qinhuangdao F - 质数之谜(DP)

题意 给定一个序列,修改最少数量的元素使得任意i属于[1,n-1],q[i]+q[i+1]都为质数,输出最小修改次数 思路 首先手玩的过程中可以发现,     如果因为前面一个数字和自己相加不是质数然后我把自己变成了奇数,那么如果我后面一个数字是偶数     可以发现自己肯定能找到另一个奇数使得和前面相加互质并且和后面相加也互质     举个例子:假设为2 8 10,我此时是8,我发现2+

2019ICPC 银川区域赛 Base62(进制转换 java)

As we already know, base64 is a common binary-to-text encoding scheme. Here we define a special series of positional systems that represent numbers using a base (a.k.a. radix) of 22 to 6262. The symbo

RMI(Remote Method Invoker) java 远程方法调用

RPC(远程过程调用 ) 的一种,初次之外PRC架构还有Hessian、dubbo等。 下面仅介绍java中自带的远程调用工具:RMI 1.对外接口: public interface IService extends Remote { public String queryName(String no) throws RemoteExceptio

CCPC2020 - 秦皇岛 - G. Good Number (数学)

亚历克斯喜欢数字。 亚历克斯认为,正整数 x x x 是好数,当且仅当 ⌊ x k ⌋ \lfloor \sqrt[k]{x} \rfloor ⌊kx ​⌋ 整除 x x x 。 你能告诉他不超过 n n n 的正整数的个数吗? 输入 输入的第一行给出了测试用例的数量 T ( 1 ≤ T ≤ 10 ) T (1 \le T \le 10) T(1≤T≤10) 。接下来是 T

(2019 CCPC 秦皇岛)E - Escape

解:这个题如果能想到每个机器人的路径都不是相同的那就很好解决了,因为在一个地方只能有一种转向的选择嘛。然后将一个点拆点四个方向就行了,(不过我交了网上几个代码都wa了,emmm #include<bits/stdc++.h>#define il inline#define pb push_back#define ms(_data) memset(_data,0,sizeof(_data))

ZOJ 3993(2017CCPC秦皇岛站M题)Safest Buildings

题目连接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3993 题目大意:        最初的防御战是以(0,0)为圆形R为半径的一个圆O1,问你当防御战缩小为最初的圆O1内的一个半径为r的小圆(小圆的圆心随意位置)时,各点的能在小圆内的概率最大的是哪个。 题目思路:       AC代码: #inc

河北职称计算机 英语考试报名,2017河北职称计算机考试报名:秦皇岛职称计算机报名入口...

【考试简介】全国专业技术人员计算机应用能力考试是一种计算机能力考试。 全国职称计算机考试可以提高计算机和网络的普及应用程度,加强信息资源的开发和利用”的精神,落实国家加快信息化建设的要求,引导全国专业技术人员学习掌握计算机知识,提高计算机的应用能力,根据原人事部《关于全国专业技术人员计算机应用能力考试的通知》(人发2001124号),从2002年开始,在全国范围内推行专业技术人员计算机应用能力考

2019ICPC南京站

A A Hard Problem 题意:给定一个正整数 n ,你需要找出最小整数 k,满足:从{1,2,⋯,n}中任意选择长度为k的子集,存在两个不同的整数 u,v∈T, 且 u 是 v 的因数。 思路:打表找规律 #include <bits/stdc++.h>#define ios ios::sync_with_stdio(0),cin.tie(0)#define PII pai