recursion - 弹珠游戏

Question

问题：有R个红色弹子，G个绿色弹子和B个蓝色弹子（R≤G≤B） 数出将它们排列成一条直线的方式的数量，使相邻的两个弹子颜色不同。

例如，R=G=B=2，答案是 30。

我尝试过使用递归，当然还有TLE：

将 r(R,B,G) 定义为将它们排列在第一个大理石为红色的位置的方式数。分别定义 b(R,B,G),g(R,B,G)。
那么 r(R, B, G) = b(R-1,B,G) + g(R-1,B,G)
答案是 r(R,B,G) + b(R,B, G) + g(R,B,G)

但是我们可以看到 r(R, B, G) = b(B, R, G) ...
所以，我们只需要一个函数 f(x,y,z)=f(y,x−1,z )+f(z,x−1,y)
答案是 f(x,y,z) + f(y,z,x) + f(z,x,y)。

时间限制为 2 秒。

我不认为动态不是 TLE，因为R、G、B <= 2e5

标签： recursionmathdynamic

Answer 1

限制递归的一些事情：

• 如果 R>G+B+1，则无法避免有 2 个相邻的红色。（G>R+B+1 & B>R+G+1 的类似论证。）
• 如果R = G + B + 1，那么您将红色与非红色交替，并且您的问题简化为您可以通过多少种方式排列G绿色和B黑色而不用担心邻接（因此应该有一个封闭形式解决方案）。（同样，G=R+B+1 和 B=R+G+1 的类似论证。）