P1540 [NOIP 2010 Senior] Machine Translation

NOIP 2010 Senior T1.

Xiao Chen’s computer has a machine translation program, which he often uses to translate English articles. The principle of this program is simple: it processes the article from start to finish and replaces each English word with its corresponding Chinese meaning. For each English word, the program first looks up the word in memory. If it is found in memory, the program uses it to translate; if it is not found, the program looks it up in a dictionary on external storage, obtains the Chinese meaning, performs the translation, and then inserts the word and its meaning into memory for future lookups. Assume the memory has $M$ slots, and each slot can store one word and its meaning. Before inserting a new word, if the number of words currently stored is at most $M-1$, the program stores the new word in an unused slot; if $M$ words are already stored, the program clears the word that entered memory the earliest to free a slot, and stores the new word. Assume an English article has length $N$ words. Given this article, how many times does the program need to consult the dictionary on external storage? At the start of translation, the memory is empty.

There are $2$ lines. The first line contains two positive integers $M, N$, representing the memory capacity and the length of the article. The second line contains $N$ non-negative integers in the order of the article; each integer (no greater than $1000$) represents an English word. Two words in the article are the same if and only if their corresponding non-negative integers are equal. Numbers on the same line are separated by a single space.

Output a single integer: the number of times the program needs to consult the dictionary.

### Sample Explanation The whole lookup process is as follows. Each line shows the memory state before the colon, for each word translation: 1. `1`: look up word 1 and load it into memory. 2. `1 2`: look up word 2 and load it into memory. 3. `1 2`: find word 1 in memory. 4. `1 2 5`: look up word 5 and load it into memory. 5. `2 5 4`: look up word 4 and load it into memory, replacing word 1. 6. `2 5 4`: find word 4 in memory. 7. `5 4 1`: look up word 1 and load it into memory, replacing word 2. A total of $5$ dictionary lookups. ### Constraints - For $10\%$ of the testdata, $M=1$, $N \leq 5$. - For $100\%$ of the testdata, $1 \leq M \leq 100$, $1 \leq N \leq 1000$. Translated by ChatGPT 5