两个字符串题目

这个学期实在是太酷毙苦逼了,第一次有这种用尽全力还是跟不上的感觉,要是人活着可以不用睡觉就好了…
天天读paper,做证明题,还有什么3DFFT,并行矩阵乘法…简直是…唉,将来找工作又能用到多少呢,还不如多刷几个算法题…

记一下这星期做的两个算法题,顺便测试下 $\LaTeX$ 插件.

1. 说的是给一个字符串, $S = \{a,b,c\}^n, n \leq 100$ ,相邻的两个字符可以转化成另一个字符,直到不能转化为止,比如”ac”=>”b”,”acc”=>”bc”=>”a”,求可以通过转化达到的最短长度.

想了下贪心,没什么把握,就DP了, 容易想到的是,如果初始字符串不是只含有一种字符,那么最后的结果最多为2,证明挺简单的.然后还有一个直观的就是最短的字符串一定是只含一种字符的.接下来就是dp方程:
设 $\mathcal{K} = \{a,b,c\}, k \in \mathcal{K}$ , $f(i , j , k)$ 表示从 $i$ 到 $j$ 这段字符串通过转化,成为只含有字符 $k$ 的字符串的最短长度.于是 $f(i , j , k)$ 可以从 $f(i + 1 , j , \mathcal{K})$ , $f(i , j - 1 , \mathcal{K})$ 以及 $f(i + 1 , j - 1 , \mathcal{K})$ 转移过来, 其中还得注意长度奇偶性什么的.Anyway,写得很麻烦,好歹过了…