首页 > 代码库 > hdu2045 不容易系列三——LELE的RPG难题 (递推方程)
hdu2045 不容易系列三——LELE的RPG难题 (递推方程)
本文出自:blog.csdn.net/svitter
原题: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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。