【题面】
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("-1n"); else printf("%dn", ans); } return 0; }
【心得】
c++数组的下标可以是字符的。
解释如下:
-
c++中字符在计算机内存储的是字符的ascii码;
-
而ascii码实质是数字,例如‘a’是97,‘a’是65;
-
如果用字符作为下标,实质就是用该字符的ascii码作为下标;
-
但是在用字符作为下标时没有数字直观,容易引起数组越界,因此不建议这样用。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599938.html