杭電 HDU ACM 2045 不容易系列之(3)―― LELE的RPG難題
來源：程序員人生 發布時間：2015-04-24 08:36:21 閱讀次數：2594次
不容易系列之(3)―― LELE的RPG困難
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 34689 Accepted Submission(s): 13913
Problem Description
人稱“AC女之殺手”的超級偶像LELE最近忽然玩起了深沉，這可急壞了眾多“Cole”（LELE的粉絲,即"可樂"）,經過量方刺探，某資深Cole終究知道了緣由，原來，LELE最近研究起了著名的RPG困難:
有排成1行的ｎ個方格，用紅(Red)、粉(Pink)、綠(Green)3色涂每一個格子，每格涂1色，要求任何相鄰的方格不能同色，且首尾兩格也不同色．求全部的滿足要求的涂法.
以上就是著名的RPG困難.
如果你是Cole,我想你1定會想盡辦法幫助LELE解決這個問題的;如果不是,看在眾多漂亮的痛不欲生的Cole女的面子上,你也不會袖手旁觀吧?
Input
輸入數據包括多個測試實例,每一個測試實例占1行,由1個整數N組成，(0<n<=50)。
Output
對每一個測試實例，請輸出全部的滿足要求的涂法，每一個實例的輸出占1行。
Sample Input
Sample Output
Author
lcy
困難 ！難在前幾項沒有初始化對！
思路：
n個格子合乎題目要求的涂色時（即稱之為合法）對應1個映照f 使f（n）即為所求值。那末接下來分析，當涂
第n個格子的時候，即要求f（n）時，遭到第n⑴個格子是不是與第1個格子相同的制約。那末接下來的問題是對第
n⑴個格子分兩種情況：假定其和第1個格子不同色彩，那末也就是說前n⑴個格子是合法的涂法可以寫為f（n⑴），
再涂最后1個格子只有1種涂法。第2種第n⑴個格子和第1個相同，那末前n⑴不合法，且此時第n⑵個格子1定和
第1個不同，那末此時前n⑵個格子一定又是合法的,且第n個格子2種涂法。那末對f（n）的貢獻為f(n⑵)*2，那末
f(n)來源于前兩種情況的和，由加法原理。f（n）=f（n⑴）+f(n⑵)*2;n》=4；
AC：
#include<iostream>
using namespace std;
int main()
{
int m;
double ls[51]={3,6,6};
for(int i=3;i<=50;i++)
ls[i]=ls[i⑴]+ls[i⑵]*2;
while(cin>>m)
printf("%.0lf
",ls[m⑴]);
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
