遇到一个木棒拼接问题，求解答。
Codancer现在由n根木棒，第i根木棒的长度为l[i]，并且每根木棒只有红、黄、蓝三种颜色。现在 codancer 想得到一根长度为L的木棍codancer 可以选择其中的一些按照一定的顺序把这若干根木棒拼接起来，但是codancer 要求相邻的两根木棒的颜色不得相同并且木棒的长度总和必须是 L。现在 codancer 想知道有多少种拼接方案（只要是存在顺序不同或者木棒不同就不是一同种方案）。由于答案比较大，因此你只需要输出答案对 1000000000+7 取余的结果即可。输入 n 和 T，代表木棒的总数和所需要构造的木棍的长度 T。接下来n行，每行两个数组 l[i] 和 c[i]，代表第 i 根木棒的长度和颜色。(1<=n<=15,1<=L<=225,1<=l[i]<=15,1<=c[i]<=3) 输出方案数对 10^9+7 取余的结果。
写回答
-
根据样例所有的排列方案为 : [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1] 考虑使用动态规划算法，令 dpi 表示在第 i 中状态中最后一根木棒是第 j 根木棒的方案数：那么可以得到转移方程为 :
最后枚举所有的可行性状态计数即可，最终时间复杂度为 n*(2^n) 
因此输入：3 3 [[1,1],[1,2],[1,3]] 输出：6 注:所有的排列方案为 : [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]2021-12-23 18:38:55赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
