Codeforces Round #267 (Div. 2)D(DFS+单词hash+简单DP)_html/css_WEB-ITnose
D. Fedor and Essay
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
After you had helped Fedor to find friends in the «Call of Soldiers 3» game, he stopped studying completely. Today, the English teacher told him to prepare an essay. Fedor didn't want to prepare the essay, so he asked Alex for help. Alex came to help and wrote the essay for Fedor. But Fedor didn't like the essay at all. Now Fedor is going to change the essay using the synonym dictionary of the English language.
Fedor does not want to change the meaning of the essay. So the only change he would do: change a word from essay to one of its synonyms, basing on a replacement rule from the dictionary. Fedor may perform this operation any number of times.
As a result, Fedor wants to get an essay which contains as little letters «R» (the case doesn't matter) as possible. If there are multiple essays with minimum number of «R»s he wants to get the one with minimum length (length of essay is the sum of the lengths of all the words in it). Help Fedor get the required essay.
Please note that in this problem the case of letters doesn't matter. For example, if the synonym dictionary says that word cat can be replaced with word DOG, then it is allowed to replace the word Cat with the word doG.
Input
The first line contains a single integer m (1?≤?m?≤?105) ? the number of words in the initial essay. The second line contains words of the essay. The words are separated by a single space. It is guaranteed that the total length of the words won't exceed 105 characters.
The next line contains a single integer n (0?≤?n?≤?105) ? the number of pairs of words in synonym dictionary. The i-th of the next n lines contains two space-separated non-empty words xi and yi. They mean that word xi can be replaced with word yi (but not vise versa). It is guaranteed that the total length of all pairs of synonyms doesn't exceed 5·105 characters.
All the words at input can only consist of uppercase and lowercase letters of the English alphabet.
Output
Print two integers ? the minimum number of letters «R» in an optimal essay and the minimum length of an optimal essay.
Sample test(s)
input
3AbRb r Zz4xR abRbaA xrzz Zxr y
output
2 6
input
2RuruRu fedya1ruruRU fedor
output
1 10
题意:先给出一些单词,然后再给出一个字典,一对一对给出,代表前面的单词可以被后面的替换
然后要求的是,将原来给出的单词用字典里的单词替换,使得含的R字符最少,如果有多种情况还要使得总字符数最少
思路:先给每种单词hash一下,可以用map实现
然后将每种单词的R字符数算出来,记为R[i],将每种单词的长度计算出来,记为L[i]
然后就是简单DP了,dp[i]表示单词 i 的最优的替换的单词,这里的 i 是单词hash后的值
这个DP可以用DFS来暴搜,先给所有单词按最优值排序,然后按顺序暴搜就好了,搜过的单词就不要重复搜了,会超时的
然后注意一下建边,如果单词 i 能被单词 j 替换,则从 j 向 i 连一条边
最后注意的是结果要用long long

핫 AI 도구

Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

AI Hentai Generator
AI Hentai를 무료로 생성하십시오.

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)

뜨거운 주제











공식 계정 웹 페이지 업데이트 캐시, 이것은 간단하고 간단하며 냄비를 마시기에 충분히 복잡합니다. 공식 계정 기사를 업데이트하기 위해 열심히 노력했지만 사용자는 여전히 기존 버전을 열었습니까? 이 기사에서는이 뒤에있는 비틀기와 회전을 살펴 보고이 문제를 우아하게 해결하는 방법을 살펴 보겠습니다. 읽은 후에는 다양한 캐싱 문제를 쉽게 처리 할 수있어 사용자가 항상 가장 신선한 콘텐츠를 경험할 수 있습니다. 기본 사항에 대해 먼저 이야기 해 봅시다. 액세스 속도를 향상시키기 위해 브라우저 또는 서버는 일부 정적 리소스 (예 : 그림, CSS, JS) 또는 페이지 컨텐츠를 저장합니다. 다음에 액세스 할 때 다시 다운로드하지 않고도 캐시에서 직접 검색 할 수 있으며 자연스럽게 빠릅니다. 그러나 이것은 또한 양날의 검입니다. 새 버전은 온라인입니다.

이 기사는 CSS를 사용한 웹 페이지에 효율적인 PNG 테두리 추가를 보여줍니다. CSS는 JavaScript 또는 라이브러리에 비해 우수한 성능을 제공하며, 미묘하거나 눈에 띄는 효과를 위해 테두리 너비, 스타일 및 색상 조정 방법을 자세히 설명합니다.

이 기사에서는 브라우저에서 직접 사용자 입력을 검증하기 위해 필요한, Pattern, Min, Max 및 Length 한계와 같은 HTML5 양식 검증 속성을 사용하는 것에 대해 설명합니다.

이 기사는 HTML & LT; Datalist & GT에 대해 논의합니다. 자동 완성 제안을 제공하고, 사용자 경험을 향상시키고, 오류를 줄임으로써 양식을 향상시키는 요소. 문자 수 : 159

이 기사는 HTML & lt; Progress & Gt에 대해 설명합니다. 요소, 그 목적, 스타일 및 & lt; meter & gt의 차이; 요소. 주요 초점은 & lt; progress & gt; 작업 완료 및 & lt; meter & gt; Stati의 경우

이 기사는 HTML & lt; meter & gt에 대해 설명합니다. 범위 내에 스칼라 또는 분수 값을 표시하는 데 사용되는 요소 및 웹 개발의 일반적인 응용 프로그램. & lt; meter & gt; & lt; Progress & Gt; 그리고 Ex

기사는 HTML5 크로스 브라우저 호환성을 보장하기위한 모범 사례에 대해 논의하고 기능 감지, 점진적 향상 및 테스트 방법에 중점을 둡니다.

이 기사는 & lt; iframe & gt; 외부 컨텐츠를 웹 페이지, 공통 용도, 보안 위험 및 객체 태그 및 API와 같은 대안을 포함시키는 태그의 목적.
