AT_joig2024_e.名前 (Name)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

JOI 君和 IOI 君决定养一只狗。首先要做的事情是给狗取一个名字。经过两人的商议，决定名字需要满足以下 $4$ 个条件。

条件 1 名字必须是由英文字母大写字母（A, B, ..., Z）和小写字母（a, b, ..., z）组成的字符串。

条件 2 JOI 君喜欢的字符串是长为 $N$ 的字符串 $S$ ，因此 $S$ 必须作为名字的一个子序列出现。

条件 3 IOI 君喜欢的字符串是长为 $M$ 的字符串 $T$ ，因此 $T$ 必须作为名字的一个子序列出现。

条件 4 为了使名字读起来方便，对于名字中任意两个相同的字符，其间必须至少有 $K$ 个其他字符。严格来说，对于任意位置不同但字符相同的两个字母，它们之间必须有至少 $K$ 个不同的字符。注意，如果 $K=0$ ，或者名字中的字母全部互不相同，则此条件自动满足。

需要注意的是，英文字母的大写和小写是有区分的。例如，A 和 a 被认为是不同的字母。

这里，名字的子序列表示从名字中删除若干（可以是 $0$ ）个字符后得到的字符串。例如，当名字为 algorithm 时，ai 和 lgtm 是该名字的子序列，但 joi 和 logarithm 不是。

两人认为名字越短越好，所以请在上述 $4$ 条件下，为狗狗取一个最短的名字。

给定 JOI 君和 IOI 君喜欢的字符串，以及整数 $K$ ，请你编写程序输出名字的最小长度。

输入格式

输入按以下格式给出。

$N$ $M$ $K$ $S$ $T$

输出格式

请输出满足条件的名字的最小长度，仅一行。

输入输出样例

输入#1
```
10 10 0
hottokeiki
hottokeiki
```
输出#1
```
10
```
输入#2
```
10 10 1
hottokeiki
hottokeiki
```
输出#2
```
11
```
输入#3
```
10 10 3
hottokeiki
hottokeiki
```
输出#3
```
15
```
输入#4
```
6 9 0
Jouhou
Orinpikku
```
输出#4
```
14
```
输入#5
```
9 7 1
CoMMiTTee
TeRRaCe
```
输出#5
```
15
```
输入#6
```
6 8 2
JOIIOI
JOIGEGOI
```
输出#6
```
9
```

说明/提示

子任务

（ $2$ 分） $S = T$ ， $K = 0$ 。
（ $7$ 分） $S = T$ ， $K = 1$ 。
（ $16$ 分） $S = T$ 。
（ $17$ 分） $K = 0$ 。
（ $13$ 分） $K = 1$ ， $N \leq 25$ ， $M \leq 25$ 。
（ $15$ 分） $K = 1$ 。
（ $20$ 分） $K \leq 2$ 。
（ $10$ 分）无其它额外限制。

样例解释 1

JOI 君和 IOI 君喜欢的字符串都是 hottokeiki。如果把狗的名字取为 hottokeiki，那么：

条件 1： 名字由大小写英文字母构成。
条件 2： 字符串 $S$ （hottokeiki）是名字 hottokeiki 的子序列。
条件 3： 字符串 $T$ （hottokeiki）是名字 hottokeiki 的子序列。
条件 4： $K=0$ ，所以条件自动满足。

这是满足所有条件的最短名字，其长度为 $10$ 。

这个输入满足子任务 $1,3,4,7,8$ 的限制。

样例解释 2

本例和样例 1 的区别只是 $K$ 的取值不同。

如果名字还是取为 hottokeiki，则条件 4不满足，因为两个 t 中间没有 $1$ 个字符。

满足所有条件的最短名字可以是 hotNtokeiki，长度为 $11$ 。

这个输入满足子任务 $2,3,5,6,7,8$ 的限制。

样例解释 3

本例和样例 1,2 的区别是 $K$ 的取值不同。

如果名字用 hotNtokeiki，则条件 4不满足，因为两个 t 之间仅隔 $1$ 个字符，两个 k 之间只有 $2$ 个字符，以及两个 i 之间仅有 $1$ 个字符。

满足所有条件的最短名字可以是 hotarutokeiyuki，长度为 $15$ 。

这个输入满足子任务 $3,8$ 的限制。

样例解释 4

JOI 君喜欢的字符串为 Jouhou，IOI 君喜欢的字符串为 Orinpikku。如果将狗的名字取为 OJouhorinpikku，那么：

条件 1： 名字由大小写英文字母构成。
条件 2： 字符串 $S$ （Jouhou）是名字 OJouhorinpikku 的子序列。
条件 3： 字符串 $T$ （Orinpikku）是名字 OJouhorinpikku 的子序列。
条件 4： $K=0$ ，所以条件自动满足。

这是一个满足所有条件的最短名字之一，长度为 $14$ 。注意，因为大小写有区分，jouhorinpikku（长度 $13$ ）等名字并不满足条件。

这个输入满足子任务 $4,7,8$ 的限制。

样例解释 5

满足所有条件的最短名字之一是 CoMaMiTeRTeRaCe，长度为 $15$ 。

这个输入满足子任务 $5,6,7,8$ 的限制。

样例解释 6

满足所有条件的最短名字是 JOIGEIGOI，长度为 $9$ 。

这个输入满足子任务 $7,8$ 的限制。

数据范围与约定

$1 \leq N \leq 500$ 。
$1 \leq M \leq 500$ 。
$0 \leq K \leq 3$ 。
$S$ 是长度为 $N$ 的仅包含大小写英文字母的字符串。
$T$ 是长度为 $M$ 的仅包含大小写英文字母的字符串。
$N, M, K$ 均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页