Topcoder 12505 CharacterBoard
我们考虑如果能够枚举长度，那么每个字符对应回原串的位置就是固定的了，这样我们就可以直接 $26$ 的剩下字符个数次方得到答案。
但是事实上字符串的长度可能到达 $10^9$ ，这么考虑肯定是不行的。但是仔细想一想会发现，对于多数长度，你的 $n \times m \le 100$ 个字符根本不会有冲突。而有冲突的长度，必然是某两个字符之间差距的约数。因此我们直接枚举每两个字符之间的差距，然后枚举这个差距的约数，然后单独计算这些长度即可。剩下的长度直接用等比数列求和。
Topcoder 12349 RockPaperScissors
实际上要做的就是条件概率的计算。由于卡牌之间不可区分，我们算出一共抽出了 $a$ 个石头，$b$ 个布，$c$ 个剪刀的情况下，下一张卡抽出第 $i$ 张卡的概率即可。
这个东西可以这样计算：先把第 $i$ 张卡丢掉再剩下的卡中算出现 $(a,b,c)$ 这种情况的概率，最后再把这张卡合并进去。这样做复杂度是 $O(n^5)$ 的。这里 $dp$ 里面有组合数，所以需要把组合数写进转移里面，不然肯定会炸精度。
最后我们再做一个 $dp$ ，设 $dp[a][b][c]$ 表示到现在抽出了 $(a,b,c)$ 这个状态，最优决策下期望得分是多少。转移就是枚举一下下一轮出什么以及下一轮来什么，选最优的转移即可。
复杂度 $O(n^5)$ ，空间 $O(n^4)$ ，需要略微卡空间。
Topcoder 12339 FencingPenguins
其实这个颜色的限制很没用，可以转化成每条选择的边不能分开两个相同颜色的企鹅，那么可以转化成某些边可以选择，求出选择若干条边，使得每个多边形内部至少有一个企鹅的方案数。
这个问题我们可以区间 $dp$ 解决。具体来说，我们设 $g[l][r][0/1]$ 表示 $l \sim r$ 没有封口，这段区间形成了一个多边形，并且这个多边形内部是否有企鹅。然后再设 $f[l][r]$ 表示 $l \sim r$ 的答案。这个题可以天然地断环成链，因为选择的是一条弦而不是弧，所以你做完后的 $f[1][n]$ 一定可以涵盖所有弦的选择。
考虑转移，对于 $g$ 我们需要枚举最后一条边在哪里，然后这条边里面 $l+1,k-1$ 用 $f$ 来转移，剩下的继续用 $g$ 来转移。还需要讨论一下最后会不会获得企鹅。对于 $f$ 我们可以枚举第一个多边形的位置，这里就需要枚举第一个多边形的起点和终点 $k,t$ ，于是转移就是 $g[k][t] \times f[t + 1][r]$ 这个东西。复杂度 $O(n^4)$ 。