USACO/twofive

这是USACO Chapter 5 .5中的OI题目Two Five的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

(转自Maigo的TJU1143题解)

　　以下叙述中，“单词”均指合法单词。
　　举个例子说明：若为单词转编码，如求单词ACF……的编码，则设一累加器，先累加以AB开头的单词的个数，再累加以ACB开头的单词的个数（这个数为0，但若已知6个字母的位置，B拐到了第2行，则可能不为0），再累加以ACD开头的单词的个数，再累加以ACE开头的单词的个数……最后加1即得答案。若为编码转单词，如求第n个单词，同样设一累加器s，先累加以AB开头的单词的个数，若s>=n 了，说明第二个字母就是B，否则继续累加以AC开头的单词的个数……直到s>=n，这样第二个字母就确定了。将最后一次累加的数减去，用类似的方法确定第三、第四……个字母，直至结束。
　　现在的问题是：如何求出以某给定序列开头的单词的个数？这个问题是用记忆化搜索解决的。用f[a,b, c,d,e](5>=a>=b>=c>=d>=e>=0)表示把前a+b+c+d+e个字母填入第1行的前a个格，第2行的前b个格……第5行的前e个格，且已经确定位置的字母各就各位时可能的单词数，那么f[0,0,0,0,0]就表示以给定序列开头的单词数。下面以求以AC开头的单词数为例说明递归求f数组的方法：

• 第一层递归安置字母A。因其位置已固定，故f[0,0,0,0,0]=f[1,0,0,0,0]，进入第二层递归计算f[1,0,0,0,0]。
• 第二层递归安置字母B。B的位置尚未固定，于是枚举所有合法位置（合法位置指左、上方均已填有字母的位置，认为第0行与第0列均已填满。此例中为12、21），分别进入第三层递归计算f[2,0,0,0,0]（这个值等于0，下面会讨论其原因）与f[1,1,0,0,0]。f [1,0,0,0,0]即等于这二者之和。
• 第三层递归安置字母C。这层递归的过程与第一层递归类似。更深层递归的过程与第二层递归类似。若在某一次递归中，需要计算的f值已经算出，则不必再递归下去，直接退出即可。

　　因为每次计算单词个数时给定的序列都不同，所以每次都必须从头递归。 (在具体实现的时候,可以像后面的程序一样,使用一个5位的6进制数来表示状态,这样可以把5维数组f降到1维)

---

• 这道题目我也是花了很长时间才理解的。。。写了一个解题报告。。。但是太长了这里放不下。。。大家如果想看的话请点击下面这个链接吧 *^_^*

http://hi.baidu.com/winterlegend/blog/item/21e465255c90e53ac89559fc.html

优化技巧

程序的实现用了一点小技巧。上文中说，B的合法位置有两个，分别是12和21。但实际上，12这个位置已经被字母C占据，只是在第二次递归时程序并不知道这一点。请看程序第26行中的这一条件：len[x[c]]+1=y[c]。如果某个位置已固定的字母的位置已被别的字母占据，那么这个条件就为假，从而求出的单词数就成了0。当然，可以在递归之前把已被占据的位置做上标记，但因为需要搜索的状态总数本来就不多（只有252种），做标记不会显著提高时间效率，反而会增加编程复杂度。
　　除上段所说的以外，还有几点可以优化的地方，如以ACB开头的单词数可不经搜索直接得到0，再如当递归深度超过了所有已固定的字母时，可直接利用版本1中的DP获得结果，而不须递归下去。然而，不加这些优化的算法的复杂度已经很低了（最坏情况下为25(25个位置)*25(每个位置可能放25个字母)*252(记忆化搜索的状态总数)*5(每个状态最多有5个合法位置)=787500），这些优化都显得不太值得。

参考代码

C

C++

Pascal