Нохой

512MB

2600

Dynamic ProgrammingStrings

Бан, Бон хоёр нохой тэжээхээр шийдэж, нохойдоо нэр өгөхөөр болжээ. Тэд хоорондоо ярилцсаны эцэст дараах дөрвөн нөхцөлийг хангасан нэрийг сонгохоор шийджээ.

Нохойны нэр нь англи цагаан толгойн том үсгүүд (A, B, …, Z) болон жижиг үсгүүдээс (a, b, …, z) бүрдсэн тэмдэгт мөр байна.
Баны хамгийн дуртай тэмдэгт мөр $S$ нь $N$ урттай. Сонгосон нэр нь $S$ -ийг дэд дараалал (subsequence) болгон агуулсан байх ёстой.
Боны хамгийн дуртай тэмдэгт мөр $T$ нь $M$ урттай. Сонгосон нэр нь мөн $T$ -г дэд дараалал болгон агуулсан байх ёстой.
Нохойны нэрийг хэлэхэд хялбар байлгахын тулд ижил тэмдэгтүүдийн хооронд дор хаяж $K$ ширхэг өөр тэмдэгт байх ёстой. Тодруулбал, өөр өөр байрлалд орших ижил хоёр тэмдэгт бүрийн хооронд дор хаяж $K$ ширхэг тэмдэгт байх ёстой. Нэрд орсон бүх тэмдэгт хоорондоо ялгаатай бол энэ нөхцөл биелсэнд тооцно.

Том, жижиг үсгийг ялгана. Жишээлбэл, A ба a нь өөр тэмдэгт юм.

Энд дэд дараалал гэдэг нь тухайн мөрөөс зарим тэмдэгтийг хасаж (огт хасахгүй байж ч болно) үлдсэн тэмдэгтүүдийг дарааллаар нь авч үүсгэсэн тэмдэгт мөрийг хэлнэ. Жишээлбэл, algorithmarena гэсэн нэрийн хувьд aithen ба lgtmare нь дэд дараалал болох боловч bogar болон logarithmarena нь дэд дараалал болохгүй.

Тэд нохойны нэр богино байх тусмаа сайн гэж үзэж байгаа тул дээрх дөрвөн нөхцөлийг хангах хамгийн богино нэрийг сонгохоор шийджээ.

Бан, Бон хоёрын дуртай тэмдэгт мөрүүд болон бүхэл тоо $K$ өгөгдсөн үед нохойны нэрийн хамгийн бага уртыг олох программ бичнэ үү.

Эх сурвалж: JOIG 2023/2024, бодлого 5 — Name, Information Olympiad in Japan; CC BY-SA 4.0.

Оролтын формат

Оролтын өгөгдөл дараах форматтай байна.

text
N M K
S
T

Гаралтын формат

Дөрвөн нөхцөлийг хангасан нохойны нэрийн хамгийн бага уртыг илэрхийлэх нэг бүхэл тоог хэвлэнэ.

Хязгаарлалт

$1 \le N \le 500$
$1 \le M \le 500$
$0 \le K \le 3$
$S$ нь англи хэлний том, жижиг үсгүүдээс тогтсон $N$ урттай тэмдэгт мөр.
$T$ нь англи хэлний том, жижиг үсгүүдээс тогтсон $M$ урттай тэмдэгт мөр.
$N$ , $M$ , $K$ нь бүхэл тоо.

Дэд бодлого

Дэд бодлого	Оноо	Нөхцөл
1	2	$S=T$ , $K=0$
2	8	$S=T$ , $K=1$
3	12	$S=T$
4	16	$K=0$
5	22	$K=1$
6	20	$K=2$
7	20	Нэмэлт хязгаарлалт байхгүй

Жишээ

Оролт1

10 10 1
banharhaar
banharhaar

Гаралт1

Оролт2

10 10 3
banharhaar
banharhaar

Гаралт2

Оролт3

9 7 1
CoPPiTTee
TeLLaCe

Гаралт3

0.1 / 64 KiB

Редактор уншиж байна...