Codeforces ラウンド #267 (ディビジョン 2)D (DFS+単語ハッシュ+単純な DP)_html/css_WEB-ITnose

D. ヒョードルとエッセイ

テストごとの制限時間

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

ヒョードルが「Call of Soldiers 3」ゲームで友達を見つけるのを手伝った後、彼は完全に勉強をやめました。今日、英語の先生は彼にエッセイを準備するように言いました。ヒョードルはエッセイを準備したくなかったので、アレックスに助けを求めました。アレックスが手伝いに来て、ヒョードルのためにエッセイを書きました。しかし、ヒョードルはそのエッセイがまったく気に入らなかった。今、ヒョードルは英語の同義語辞書を使用してエッセイを変更しようとしています

ヒョードルはエッセイの意味を変更したくありません。したがって、彼が行う唯一の変更は、辞書の置換ルールに基づいて、エッセイの単語をその同義語の 1 つに変更することです。ヒョードルはこの操作を何度でも実行できます。

その結果、ヒョードルは«R»という文字（大文字と小文字は関係ありません）ができるだけ含まれないエッセイを取得したいと考えています。 «R» の数が最小のエッセイが複数ある場合、彼は最小の長さのエッセイを取得したいと考えています (エッセイの長さは、エッセイ内のすべての単語の長さの合計です)。ヒョードルが必要な作文を手に入れるのを手伝ってください。

この問題では、文字の大文字と小文字は関係ないことに注意してください。たとえば、同義語辞書で「cat」という単語を「DOG」という単語に置き換えることができると記載されている場合、「Cat」という単語を「doG」という単語に置き換えることができます。

入力

最初の行には、単一の整数 m (1? ≤?m?≤?105) ?最初のエッセイの単語数。 2行目にはエッセイの単語が含まれています。単語は単一のスペースで区切られます。単語の合計の長さが 105 文字を超えないことが保証されています。

次の行には、単一の整数 n (0?≤?n?≤?105) ? が含まれます。同義語辞書内の単語のペアの数。次の n 行の i 番目には、スペースで区切られた 2 つの空でない単語 xi と yi が含まれます。これらは、単語「xi」を単語「yi」に置き換えることができる（ただしその逆はできない）ことを意味します。同義語のすべてのペアの合計長が 5 · 105 文字を超えないことが保証されます。

入力時のすべての単語は、英語のアルファベットの大文字と小文字のみで構成できます。

出力

2 つ出力します。整数?最適なエッセイの最小文字数«R»と最適なエッセイの最小長

サンプルテスト

入力

出力

input

れーれー

出力

题意: 先给出いくつかの单词、その後再给出一字典、一对一軙出、前面の荕词を後面の代替として表すことができます

その後要求即ち、将来来出の单词用字典里の荕词代替、含有する R 字符を最少にする、如果多种情况还要使用总字数最少

思路：先给每种单词ハッシュ一下，マップを使用できます

その後、R[i] として承認され、L[i] として承認されます

然后就是简单DP了、dp[i]は、荕词 i の最も好ましい代替荕词、ここの i は荕词ハッシュ後の値です この DP は DFS を使用して攻撃できます。すべての单词按最优值排序，然后按顺序暴搜就好了，搜过的单词不要重复搜了，会超時的

然后注意一下建边，如果单词 i 能被单词 j 交代，则从 j 向 i 连一条边

最後に注意すべきことは、結果はlong long で表現する必要があるということです