首页 > ACM题库 > HDU-杭电 > hdu 2569 彼岸-动态规划-[解题报告]C++
2014
02-10

hdu 2569 彼岸-动态规划-[解题报告]C++

彼岸

问题描述 :

突破蝙蝠的包围,yifenfei来到一处悬崖面前,悬崖彼岸就是前进的方向,好在现在的yifenfei已经学过御剑术,可御剑轻松飞过悬崖。
现在的问题是:悬崖中间飞着很多红,黄,蓝三种颜色的珠子,假设我们把悬崖看成一条长度为n的线段,线段上的每一单位长度空间都可能飞过红,黄,蓝三种珠子,而yifenfei必定会在该空间上碰到一种颜色的珠子。如果在连续3段单位空间碰到的珠子颜色都不一样,则yifenfei就会坠落。
比如经过长度为3的悬崖,碰到的珠子先后为 “红黄蓝”,或者 “蓝红黄” 等类似情况就会坠落,而如果是 “红黄红” 或者 “红黄黄”等情况则可以安全到达。
现在请问:yifenfei安然抵达彼岸的方法有多少种?

输入:

输入数据首先给出一个整数C,表示测试组数。
然后是C组数据,每组包含一个正整数n (n<40)。

输出:

输入数据首先给出一个整数C,表示测试组数。
然后是C组数据,每组包含一个正整数n (n<40)。

样例输入:

2
2
3

样例输出:

9
21

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2569

题意:中文。

mark:水递推。很容易得到方程dp[i] = 2*dp[i-1]+dp[i-2]。不过dp[0] = 3。注意要用long long。

代码:

# include <stdio.h>
 
 
 long long dp[45] = {3,3} ;
 
 
 int main ()
 {
     int T, n, i ;
     for (i = 2 ; i <= 40 ; i++)
         dp[i] = 2*dp[i-1]+dp[i-2] ;
     scanf ("%d", &T) ;
     while (T--)
     {
         scanf ("%d", &n) ;
         printf ("%I64d\n", dp[n]) ;
     }
     return 0 ;
 }

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/04/27/2472914.html


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢