HBC24761小y的序列,数据结构,STL[USACO 2010 Dec G]Threatening Letter题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

FJ has had a terrible fight with his neighbor and wants to send him a nasty letter, but wants to remain anonymous. As so many before him have done, he plans to cut out printed letters and paste them onto a sheet of paper. He has an infinite number of the most recent issue of the Moo York Times that has N (1

FJ has had a terrible fight with his neighbor and wants to send him a nasty letter, but wants to remain anonymous. As so many before him have done, he plans to cut out printed letters and paste them onto a sheet of paper. He has an infinite number of the most recent issue of the Moo York Times that has N (1 <= N <= 50,000) uppercase letters laid out in a long string (though read in as a series of shorter strings). Likewise, he has a message he'd like to compose that is a single long string of letters but that is read in as a set of shorter strings. Being lazy, he wants to make the smallest possible number of cuts. FJ has a really great set of scissors that enables him to remove any single-line snippet from the Moo York Times with one cut. He notices that he can cut entire words or phrases with a single cut, thus reducing his total number of cuts. What is the minimum amount of cuts he has to make to construct his letter of M (1 <= M <= 50,000) letters? It is guaranteed that it is possible for FJ to complete his task. Consider a 38 letter Moo York Times: THEQUICKBROWNFOXDO GJUMPSOVERTHELAZYDOG from which FJ wants to construct a 9 letter message: FOXDOG DOG These input lines represent a pair of strings: THEQUICKBROWNFOXDOGJUMPSOVERTHELAZYDOG FOXDOGDOG Since "FOXDOG" exists in the newspaper, FJ can cut this piece out and then get the last "DOG" by cutting out either instance of the word "DOG". Thus, he requires but two cuts.

标签： HBC24761小y的序列 数据结构 STL[USACO 2010 Dec G]Threatening Letter题解