HDU 2045 不容易系列之(3)—— LELE的RPG難題 (動(dòng)態(tài)規(guī)劃)
[導(dǎo)讀]題目鏈接：HDU 2045
題面：
不容易系列之(3)—— LELE的RPG難題
Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 6
題目鏈接：HDU 2045
題面：
不容易系列之(3)—— LELE的RPG難題 Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 45099????Accepted Submission(s): 18054
Problem Description 人稱“AC女之殺手”的超級(jí)偶像LELE最近忽然玩起了深沉，這可急壞了眾多“Cole”（LELE的粉絲,即"可樂(lè)"）,經(jīng)過(guò)多方打探，某資深Cole終于知道了原因，原來(lái)，LELE最近研究起了著名的RPG難題:
有排成一行的ｎ個(gè)方格，用紅(Red)、粉(Pink)、綠(Green)三色涂每個(gè)格子，每格涂一色，要求任何相鄰的方格不能同色，且首尾兩格也不同色．求全部的滿足要求的涂法.
以上就是著名的RPG難題.
如果你是Cole,我想你一定會(huì)想盡辦法幫助LELE解決這個(gè)問(wèn)題的;如果不是,看在眾多漂亮的痛不欲生的Cole女的面子上,你也不會(huì)袖手旁觀吧?
?
Input 輸入數(shù)據(jù)包含多個(gè)測(cè)試實(shí)例,每個(gè)測(cè)試實(shí)例占一行,由一個(gè)整數(shù)N組成，(0
Output 對(duì)于每個(gè)測(cè)試實(shí)例，請(qǐng)輸出全部的滿足要求的涂法，每個(gè)實(shí)例的輸出占一行。
?
Sample Input 1 2 ?
Sample Output 3 6 ?
Author lcy
題意：
?? 求三種顏色上色，相鄰位不同，首尾不同的方案數(shù)。
解題：
? dp[i][j][k]，表示第i位涂的是顏色j，它的首位涂的是顏色i的方案數(shù)，最后統(tǒng)計(jì)時(shí)，只要確保最后一位不和首位相同即可。
?
#include
#include
#include
#include
#define eps 1e-20
#define LL long long
using namespace std;
LL dp[55][3][3];
LL ans;
int main()
{
memset(dp,0,sizeof(dp));
dp[1][0][0]=1;
dp[1][1][1]=1;
dp[1][2][2]=1;
for(int i=2;i<=50;i++)
{
for(int j=0;j<=2;j++)
{
for(int k=0;k<=2;k++)
{
if(k!=j)
{
dp[i][j][0]+=dp[i-1][k][0];
dp[i][j][1]+=dp[i-1][k][1];
dp[i][j][2]+=dp[i-1][k][2];
}
}
}
}
int n;
while(~scanf("%d",&n))
{
if(n==1)
{
printf("3n");
continue;
}
ans=0;
//確保不同
ans+=dp[n][0][1]+dp[n][0][2];
ans+=dp[n][1][0]+dp[n][1][2];
ans+=dp[n][2][0]+dp[n][2][1];
printf("%lldn",ans);
}
return 0;
} 
下載文檔
