【题解】Building Strings Gym - 102152E
2020-03-31 16:02:40来源:博客园 阅读 ()
【题解】Building Strings Gym - 102152E
【题面】
You are given a string s of length n consisting of lowercase English letters. This string can be used to build other strings. The cost of each letter in s is given by another string c of length n consisting of digits, such that the cost of using the letter si is ci coins.
Also, you are given another string p of length m consisting of unique lowercase English letters. Your task is to find the minimum cost to build string p by using the letters of s. Can you?
Input
The first line contains an integer T (1≤T≤500) specifying the number of test cases.
The first line of each test case contains two integers n and m (1≤n≤103,1≤m≤26), in which n is the length of strings s and c, and m is the length of string p.
Then 3 lines follow, each line contains a string, giving the string s, c, and p, respectively. Both strings s and p contains only lowercase English letters, while string c contains only digits. Also, string p is consisting of unique letters.
Output
For each test case, print a single line containing the minimum cost of building the string p by using the letters of string s. If string p cannot be built using string s, print −1.
Example
Input
3
4 2
abcd
1234
ac
4 4
abcd
1234
abec
5 3
abcba
24513
acb
Output
4
-1
8
Note
In the first test case, you have to use the 1st and 3rd letters of string s to build string p. So, the total cost is 1+3=4.
In the second test case, you cannot build string p using s because the letter ‘e’ from p does not exist in s. So, the answer is −1.
In the third test case, the optimal way is to use the 1st, 3rd, and 4th letters of string s to build p. So, the total cost is 2+5+1=8.
【AC代码】
#include<iostream> #include<cstdio> #include<cstring> using namespace std; char a[1005]; char str[1005]; char b[1000]; int main() { int t, n, m, i, j, k; scanf("%d", &t); while (t--) { int t[1005]; memset(t, -1, sizeof(t)); scanf("%d%d", &n, &m); scanf("%s", str); scanf("%s", a); for (i = 0; i < n; i++) { if (t[str[i]] > a[i]-'0'||t[str[i]]==-1) t[str[i]] = a[i]-'0'; } int ans = 0; scanf("%s", b); int flag = 0; for (i = 0; i < strlen(b); i++) { if (t[b[i]] == -1) { flag = 1; break; } ans += t[b[i]]; } if (flag) printf("-1\n"); else printf("%d\n", ans); } return 0; }
【心得】
C++数组的下标可以是字符的。
解释如下:
-
C++中字符在计算机内存储的是字符的ASCII码;
-
而ASCII码实质是数字,例如‘a’是97,‘A'是65;
-
如果用字符作为下标,实质就是用该字符的ASCII码作为下标;
-
但是在用字符作为下标时没有数字直观,容易引起数组越界,因此不建议这样用。
原文链接:https://www.cnblogs.com/xxxsans/p/12605415.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:C++抓图服务
- Unsolved --> Solved OJ思路题解 2020-05-30
- Building & Debugging chromium on CLion for Linu 2020-05-19
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- GPLT-天梯赛-题解目录 2020-03-22
- CodeForces 1320D - Reachable Strings 2020-03-20
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash