【题解】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++数组的下标可以是字符的。

 

解释如下：

1. c++中字符在计算机内存储的是字符的ascii码；

2. 而ascii码实质是数字，例如‘a’是97,‘a'是65；

3. 如果用字符作为下标，实质就是用该字符的ascii码作为下标；

4. 但是在用字符作为下标时没有数字直观，容易引起数组越界，因此不建议这样用。