原题:http://acm.hdu.edu.cn/showproblem.php?pid=2045
题意:中文不用我说了吧。
这个题目的关键就在于递推方程——以及错误的测试数据
首先这个题目就是简单的置换群着色问题——
去除了反转的问题,难一点的大家可以看P197(离散数学,高等教育出版社)
我在做这个题目的时候首先被f [ 1 ] = 3 困扰了。。拜托,根本不符合题意好吗- =一个格子能说是首尾颜色不同吗?
后来写错了递推方程——f [ n ] = f [ n - 1 ] + 3 * f [ n - 2 ],把 f [ n - 1 ] 的情况多考虑了一遍- = 。
正确的方程应该是 —— f [ n ] = f [ n - 1 ] + 2 * f [ n - 2 ] , n >= 4; (去除了f [ 1 ] = 3 这个坑爹的干扰。)
写成lln是为了防止超范围——写完以后记得DEBUG一下看看有没有超范围——
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define lln long long int lln f[51]; void ace() { memset(f, 0x3f, sizeof(f)); int i; f[1] = 3; f[2] = 6; f[3] = 6; for(i = 4; i <= 50; i++) { f[i] = f[i - 1] + 2 * f[i - 2]; } int t; while(~scanf("%d", &t)) { printf("%I64d\n", f[t]); } } int main() { ace(); return 0; }
hdu2045 不容易系列三——LELE的RPG难题 (递推方程),布布扣,bubuko.com
hdu2045 不容易系列三——LELE的RPG难题 (递推方程)
原文:http://blog.csdn.net/svitter/article/details/24866179