数学|HDU - 2045不容易系列之(3)离散 - 置换群着色
题目链接：HDU - 2045
题目描述：
有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，
要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法
Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0
对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。
Sample Input
1
2
Sample Output
3
6
这个题目的关键就在于递推方程——以及错误的测试数据
首先这个题目就是简化的置换群着色问题——
去除了反转的问题，难一点的可以参考P197（离散数学，高等教育出版社）
这题的难度主要在递推公式的找寻，一般从最后开始找规律。
思路如下：
n个方格的涂色方案可以由n - 1的涂色方案追加一个得出，分两种情况：
【数学|HDU - 2045不容易系列之(3)离散 - 置换群着色】1.在n - 1的合法涂色方案后追加一个方格，由于合法方案的首尾颜色不同，因此第n个方格的颜色必定是这两种颜色之外的一种，即方案数为f[n - 1]。
2.在n - 1的不合法涂色方案（首尾颜色相同）后追加一个合法的涂色方格，也可能使其成为长度为n的合法涂色方案，
而这种不合法涂色方案的结构必定是f[n - 2]合法方案 + 首格颜色 + 首格外的两种颜色，即方案数为2 * f[n - 2]。
#include
typedef long long ll ;
ll dp[53] ;
int main() {
dp[1] = 3 ;
dp[2] = 6 ;
dp[3] = 6 ;
for(int i=4 ;
i<=53 ;
i++ ) {
dp[i] = dp[i-1] + 2 * dp[i-2] ;
//数据范围大用longlong
}
int n ;
while( scanf("%d" , &n ) != EOF ) {
printf("%lld\n" , dp[n] ) ;
}
return 0 ;
}推荐阅读
- 数学大作战
- 2019.11.14号总结
- 五年级数学上册期中考试质量分析
- 思维导图让你换一种打开方式学数学
- 读《吴正宪给小学数学教师的建议》有感
- 湘潭大学“三下乡”（羊牯村采访）
- 【思维导图实战派】刻意练习计划“遇见……”|【思维导图实战派】刻意练习计划“遇见……” 1/300 人教版数学五下第三单元《正方体和长方体的认识》
- 俄语小数、分数、百分数、及简单数学公式的读法
- 拨动一代代数学家心弦的圆周与直径之比——圆周率发展简史
- 吴正宪老师让学生爱上数学的四点经验