玩弹珠的游戏

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

Answer 1

有些事情可以限制递归：

如果

• 如果R>G+B+1，那么就没有办法避免有两个相邻的红色。( G>R+B+1 &B>R+G+1.的类似论点)
• ，如果是R=G+B+1，那么你可以选择红色和非红色，你的问题被归结为你能用多少种方法来安排G绿色和B黑色，担心邻接(因此应该有一个封闭形式的解决方案)。(同样，G=R+B+1和B=R+G+1.的类似论点)