美食博覽會 (APCS 2021-09 高級)

問題描述

獅子國每年都會舉辦美食展覽，由於全國店家都想參展，所有店家要在一個月前就先去登記。今年搶到第 \(1\) 號攤位的是真好吃鳳梨酥，第 \(2\) 號攤位是天天來牛肉麵，預計會有成千上萬個店家來設攤位，排成一條綿延不絕看不到盡頭的長龍。因參展店家眾多，每個店家的攤位僅提供一種美食，但某些美食可能會出現在多個攤位。

國王是一位美食愛好者，他雖日理萬機，但每年都會率領大臣擔任試吃員。國王與大臣們商量後決定每個人從某一個攤位開始，依編號逐一造訪下個攤位，造訪的同時也要品嚐該攤位所提供的美食，但國王與大臣都不願意吃兩攤相同的美食，所以如果下一攤的美食是他已經造訪吃過的品項，他就會不吃且離開展覽。

為了鼓勵參展店家，國王希望自己與大臣們能造訪的美食攤位愈多愈好，於是吩咐獅子國的程式設計師，請他寫程式來協助擬定這次的參展行程。給定每個攤位提供的美食品項，請寫一個程式計算國王與大臣們最多能造訪幾個不同的攤位。

輸入格式

第一行有二個整數 \(n\) 與 \(k\)，分別表示今年參展的攤位數以及試吃員總人數(包含國王與大臣)，其中 \(1 \le n \le 10^6\)，\(1 \le k \le 20\) 且 \(n \times k \le 5\times 10^6\)。第二行有 \(n\) 個數字，每個數字代表一種美食品項，其中第 \(i\) 個數字為編號 \(i\) 的攤位所提供的美食品項，此 \(n\) 個數字皆為小於 \(10^5\) 的非負整數。

輸出格式

一個整數，為國王與大臣們最多能造訪的攤位數。

範例一：輸入

5 1
1 2 1 3 1

範例一：正確輸出

3

範例一說明

試吃員只有國王 \(1\) 人，可從攤位 \(2\) 開始，依序造訪攤位 \(2\)、\(3\) 及 \(4\)。共可拜訪 \(3\) 個提供不同美食的攤位，品嚐到的美食為 \((2,1,3)\)。

範例二：輸入

10 3
1 7 1 3 1 4 4 2 7 4

範例二：正確輸出

8

範例二說明

第一位從攤位 \(2\) (美食品項 \(7\)) 開始造訪，品嚐到的美食為 \((7,1,3)\)；第二位從攤位 \(5\) (美食品項 \(1\)) 開始造訪，品嚐的美食為 \((1,4)\)；第三位從攤位 \(7\) (美食品項 \(4\)) 開始造訪，品嚐的美食為 \((4,2,7)\)，三人一共造訪 \(3 + 2 + 3 = 8\) 個攤位。注意，第二位如果從攤位 \(4\) 開始造訪，品嚐到的美食為 \((3,1,4)\)，但造訪的攤位總數還是 \(8\)，因為攤位 \(4\) 雖被第一與第二人重複造訪，但只會計算為一攤。

評分說明

每筆測試資料執行時間限制為 \(1\) 秒，Python 程式的執行時間限制為 \(4\) 秒，依正確通過測資筆數給分，其中：

第 \(1\) 子題組 \(50\) 分：\(k = 1\)。

第 \(2\) 子題組 \(50\) 分：無額外限制。

題目來源

試題來源：程式實作 2021 年 9 月