『GROI-R2』不空白的画布

Luogu

IDLGP9653

Time1000ms

Memory512MB

DifficultyP3

贪心洛谷原创O2优化洛谷月赛

我们都知道爱丽丝躲起来之后，坦尼尔坐在了空白画布面前，拿起炭笔开始作画。但是现在画布已经不再空白，因为画布上已经有了当下的风景。我们设画布的长度是 $n$，每一单位长度上的颜色可以用一个在 $[1,k]$ 范围内的正整数表示。坦尼尔还要画他已经翻了的茶杯。每一次作画，他可以选定画布上的任意一个位置，然后将这个位置上的颜色涂改成 $[1,k]$ 范围内的任意正整数。最后，我们都知道这幅画是有记忆的。定义画上留下的记忆碎片数量为画上的**相同颜色连续块个数**。现在坦尼尔想知道，如果给定他作画的次数**上限**，那么画上的记忆碎片个数**最多**有多少。 **形式化题面** 你有连续的 $n$ 个方格，每个方格上有一个初始颜色 $c_i$，且保证 $1\le c_i \le k$。你可以操作**至多** $m$ 次，每个操作为改变某个方格颜色，要求改变后的颜色范围仍在 $[1,k]$ 内。我们称一个**极长相同颜色连续段**为一块，要求求出经过至多 $m$ 次操作后的**最多**块数。 ## Input 本题有多组测试数据。第一行输入一个正整数 $T$ 表示数据组数。对于每组测试数据，第一行输入三个正整数 $n,m,k$，表示画布的长度，坦尼尔作画的次数上限和颜色的取值范围。第二行输入一个长度为 $n$ 的整数序列 $c$，表示画布上每个位置的初始颜色。 ## Output 对于每组测试数据，输出一行一个正整数，表示记忆碎片最多有多少个。 [samples] ## Note **样例解释** 对于第一组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，得到 $\{c_n\}=\{2,1,2\}$，块数为 $3$。对于第二组测试数据，坦尼尔可以将从左到右的第二个位置涂成颜色 $1$，将从左到右的第三个位置涂成颜色 $3$，得到 $\{c_n\}=\{2,1,3,2,3\}$，块数为 $5$。 **数据范围** **本题采用捆绑测试**。 | $\text{Subtask}$ | $\sum n\le$ | $m\le$ | $k\le$ | 分值 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $10$ | $3$ | $10$ | | $2$ | $5\times 10^5$ | $1$ | $5\times 10^5$ | $10$ | | $3$ | $10^3$ | $10^3$ | $10^3$ | $15$ | | $4$ | $5\times 10^5$ | $5\times 10^5$ | $3$ | $25$ | | $5$ | $5\times 10^5$ | $5\times 10^5$ | $5\times 10^5$ | $40$ | 对于 $100\%$ 的数据满足 $1\le n\le 5\times 10^5$，$1\le \sum n\le 5\times 10^5$，$1\le m\le n$，$3\le k \le 5\times 10^5$，$1\le c_i\le k$。

Samples

Input #1

Output #1

3
5

API Response (JSON)

{
  "problem": {
    "name": "『GROI-R2』 不空白的画布",
    "description": {
      "content": "我们都知道爱丽丝躲起来之后，坦尼尔坐在了空白画布面前，拿起炭笔开始作画。 但是现在画布已经不再空白，因为画布上已经有了当下的风景。我们设画布的长度是 $n$，每一单位长度上的颜色可以用一个在 $[1,k]$ 范围内的正整数表示。 坦尼尔还要画他已经翻了的茶杯。每一次作画，他可以选定画布上的任意一个位置，然后将这个位置上的颜色涂改成 $[1,k]$ 范围内的任意正整数。 最后，我们都知道这幅画",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9653"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "我们都知道爱丽丝躲起来之后，坦尼尔坐在了空白画布面前，拿起炭笔开始作画。\n\n但是现在画布已经不再空白，因为画布上已经有了当下的风景。我们设画布的长度是 $n$，每一单位长度上的颜色可以用一个在 $[1,k]$ 范围内的正整数表示。\n\n坦尼尔还要画他已经翻了的茶杯。每一次作画，他可以选定画布上的任意一个位置，然后将这个位置上的颜色涂改成 $[1,k]$ 范围内的任意正整数。\n\n最后，我们都知道这幅画...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments

『GROI-R2』 不空白的画布

『GROI-R2』不空白的画布