ConversionMachine

作者：高睿泉

关键词：动态规划

题目大意

给定两个相同长度的单词$w_{1},w_2$（都只含有'$a$','$b$','$c$'三种字符）。已知'$a$'变成'$b$'（'$b$'无法直接变成'$a$',下同）,'$b$'变成'$c$','$c$'变成'$a$'的代价分别为$c_1,c_2,c_3$，求把$w_1$变为$w_2$且总代价不超过$maxCost$的方案数。

数据范围

$|w_1|=|w_2|\leq 11;\; maxCost,c_1,c_2,c_3\leq 10^{9}$

算法一

每一种方案中，对于每个字母，一定是先把它变成正确的之后再进行若干组3次的循环变换。由于每个字母第一次变成正确的代价是固定的，任意一个字母的任意一组3次的循环变换的代价是固定的，所以如果所有的字母都变成正确的，变换的次数一定是和变换的代价一一对应的。同样我们也可以由此算出最多可以进行变换的次数$m$。由于变换次数越小，对应的代价也一定越小，所以一个方案合法当且仅当保证变换的次数小于等于最大变换次数$m$且每个字母都变成目标字母。

根据上面的结论，可以利用动态规划解决。$dp_{i,j,k}$表示用了$i$次变换有$j$个字母还差一次变成正确，$k$个字母还差两次变成正确的方案数。每次转移的时候枚举把哪一类的字母变换一次。时间复杂度$O(m|w_1|^2)$。

可以利用矩阵乘法优化转移，时间复杂度$O(|w_1|^6log\;m)$。