国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php框架 > codeigniter > Codeforces 467D Fedor and Essay(bfs)

Codeforces 467D Fedor and Essay(bfs)

来源:程序员人生   发布时间:2014-10-10 08:00:00 阅读次数:4068次

题目链接:Codeforces 467D Fedor and Essay

题目大意:给定一个含n个单词的文本,然后给定m种变换,要求变换后r的个数尽量少,长度尽量短,不区分大小写。

解题思路:bfs,将每个单词处理成长度以及r的个数,然后从最优的开始更新即可,类似dp。

#include <cstdio> #include <cstring> #include <map> #include <string> #include <vector> #include <queue> #include <iostream> #include <algorithm> using namespace std; const int maxn = 1e5+5; typedef long long ll; typedef pair<ll, ll> pii; int M, N, sz, W[maxn]; map<string, int> V; vector<int> g[maxn * 3]; pii vec[maxn*3]; void add (string& s) { ll len = s.length(), cnt = 0; for (int j = 0; j < len; j++) { if (s[j] >= 'A' && s[j] <= 'Z') s[j] = s[j] - 'A' + 'a'; if (s[j] == 'r') cnt++; } if (!V.count(s)) { V[s] = sz; vec[sz++] = make_pair(cnt, len); } } void init () { sz = 0; string s, e; cin >> M; for (int i = 0; i < M; i++) { cin >> s; add(s); W[i] = V[s]; } cin >> N; for (int i = 0; i < N; i++) { cin >> s >> e; add(s); add(e); g[V[e]].push_back(V[s]); } } void solve () { queue<int> que; for (int i = 0; i < sz; i++) que.push(i); while (!que.empty()) { int idx = que.front(); pii u = vec[idx]; que.pop(); for (int i = 0; i < g[idx].size(); i++) { int v = g[idx][i]; if (vec[v] > u) { vec[v] = u; que.push(v); } } } ll len = 0, cnt = 0; for (int i = 0; i < M; i++) { cnt += vec[W[i]].first; len += vec[W[i]].second; } cout << cnt << " " << len << endl; } int main () { init(); solve(); return 0; }
生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生