yukicoder-422

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/422 No.422 文字列変更 (Hard)] ==

=== Description ===

{{{
#!html
<p>有一个长度为$n$的字符串$S$和一个长度为$m$的字符串$T$，它们由字符'A'，'T'，'G'，'C'组成。</p>

<p>现在需要把$S$变成$T$，你可以进行如下三种操作：
<ul>
<li>置换：选择一个$S_i$，把它变成'A'，'T'，'G'，'C'中某一个，代价是5。</li>
<li>删除：删除$S$任意一个子串，可以删除空串。如果删了$N$个字符，那么代价是$9+2(N-1)$。</li>
<li>插入：在$S$的任意位置插入一个由'A'，'T'，'G'，'C'组成的字符串。如果插入了$N$个字符，那么代价是$9+2(N-1)$。</li>
</ul>
</p>

<p>求一个代价和最小的操作序列，并输出方案。如果你删了某个字符，在$S$对应位置显示'-'，如果你插入了一个字符，在$T$对应位置显示'-'。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$n$ $m$<br>
$S$<br>
$T$
</p>

<p>$1 \le n, m \le 1200$</p>
}}}

=== Output ===

{{{
#!html
<p>第一行输出最小代价，第二行和第三行输出方案。如果有多个方案，输出任意一个即可。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
20 24
GAGTGGATCTGCGAATCTTG
GAGTTCTGTACTAAGCGCCGTGTC
</pre>
}}}
输出
{{{
#!html
<pre>
61
GAGTGGATCTG--CGAATC-----TTG
GAGT---TCTGTACTAAGCGCCGTGTC
</pre>
}}}

No.422 文字列変更 (Hard)

Description

有一个长度为$n$的字符串$S$和一个长度为$m$的字符串$T$，它们由字符'A'，'T'，'G'，'C'组成。

现在需要把$S$变成$T$，你可以进行如下三种操作：

• 置换：选择一个$S_i$，把它变成'A'，'T'，'G'，'C'中某一个，代价是5。
• 删除：删除$S$任意一个子串，可以删除空串。如果删了$N$个字符，那么代价是$9+2(N-1)$。
• 插入：在$S$的任意位置插入一个由'A'，'T'，'G'，'C'组成的字符串。如果插入了$N$个字符，那么代价是$9+2(N-1)$。

求一个代价和最小的操作序列，并输出方案。如果你删了某个字符，在$S$对应位置显示'-'，如果你插入了一个字符，在$T$对应位置显示'-'。

Input

$n$ $m$
$S$
$T$

$1 \le n, m \le 1200$

Output

第一行输出最小代价，第二行和第三行输出方案。如果有多个方案，输出任意一个即可。

Sample

Sample 1

输入

20 24GAGTGGATCTGCGAATCTTGGAGTTCTGTACTAAGCGCCGTGTC

输出

61GAGTGGATCTG--CGAATC-----TTGGAGT---TCTGTACTAAGCGCCGTGTC