http://codeforces.com/contest/959/problem/B
思路: 每一个单词对应着在原句子中的索引号,每个索引号对应着组号,每个组号对应着cost值。
用第一个例子来分析:
group | index | cost |
---|---|---|
1 | 1 | 100 |
2 | 3 | 1 |
3 | 2 | min(1, 10) = 1 |
3 | 5 | min(1, 10) = 1 |
4 | 4 | 5 |
所求句子为”i am the second” “i”在原句子中的索引号为1,对应第一组,cost为100 “am”在原句子中的索引号为3,对应第二组,cost为1 “the”在原句子中的索引号为4,对应第四组,cost为5 “second”在原句子中的索引号为5,对应第三组,cost为1 所以,结果为100 + 1 + 5 + 1 = 107
#include <iostream>
#include <map>
using namespace std;
map<string,int> mp;
int a[100005],cost[100005],group[100005];
int main()
{
int n,k,m;
// The 1st line
cin >> n >> k >> m;
// The 2nd line
for (int i=1;i<=n;i++)
{
string s;
cin >> s;
mp[s]=i;
}
// The 3rd line
for (int i=1;i<=n;i++)
{
cin >> a[i];
// initialize a big number, 2^30
cost[i]=(1<<30);
}
// The next k lines
for (int groupI=1;groupI<=k;groupI++)
{
int x;
cin >> x;
while(x--)
{
int index;
cin >> index;
group[index]=groupI;
cost[groupI]=min(cost[groupI],a[index]);
}
}
long long ans=0;
// The last line
while(m--)
{
string s;
cin >> s;
// mp[s] means index
ans+=cost[group[mp[s]]];
}
cout << ans;
}