131
技術社區[雲棲]
【端午小練】HDU2047-阿牛的EOF牛肉串
阿牛的EOF牛肉串
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19508 Accepted Submission(s): 9119
Problem Description
今年的ACM暑期集訓隊一共有18人，分為6支隊伍。其中有一個叫做EOF的隊伍，由04級的阿牛、XC以及05級的COY組成。在共同的集訓生活中，大家建立了深厚的友誼，阿牛準備做點什麼來紀念這段激情燃燒的歲月，想了一想，阿牛從家裏拿來了一塊上等的牛肉幹，準備在上麵刻下一個長度為n的隻由"E" "O" "F"三種字符組成的字符串（可以隻有其中一種或兩種字符，但絕對不能有其他字符）,阿牛同時禁止在串中出現O相鄰的情況，他認為，"OO"看起來就像發怒的眼睛，效果不好。
你，NEW ACMer,EOF的崇拜者，能幫阿牛算一下一共有多少種滿足要求的不同的字符串嗎？
PS: 阿牛還有一個小秘密，就是準備把這個刻有 EOF的牛肉幹，作為神秘禮物獻給杭電五十周年校慶，可以想象，當校長接過這塊牛肉幹的時候該有多高興！這裏，請允許我代表杭電的ACMer向阿牛表示感謝！
再次感謝！
Input
輸入數據包含多個測試實例,每個測試實例占一行,由一個整數n組成，(0<n<40)。
Output
對於每個測試實例，請輸出全部的滿足要求的塗法，每個實例的輸出占一行。
Sample Input
1
2
Sample Output
3
8
Author
lcy
Source
遞推求解專題練習（For Beginner）
第一步：先用DFS深搜來算出所有可能的情況，將前幾種情況輸出來，之後找規律
測試代碼：（不是AC代碼，隻是為了得到數據）
#include<stdio.h>
#include<string.h>
int num;
void Found(char s,int sum,int n)
{
if(sum==n)
{
num++;
return;
}
if(s=='O')
{
Found('F',sum+1,n);
Found('E',sum+1,n);
}
else
{
Found('F',sum+1,n);
Found('O',sum+1,n);
Found('E',sum+1,n);
}
}
int main()
{
int i,j,n;
while(scanf("%d",&n)!=EOF)
{
num=0;
Found('E',1,n);
Found('O',1,n);
Found('F',1,n);
printf("%d\n",num);
}
return 0;
}
得到前6個的規律：
1 3
2 8
3 22
4 60
5 164
6 448
可以看出：本數=前一個數*2+前一個數的前一個數*2；
第二步，找到規律後，用數組將可能數用找到的規律存起來，之後直接輸出答案即可！
AC代碼：
#include<stdio.h>
#include<string.h>
__int64 a[100];
int main()
{
int i,j,n;
a[1]=3,a[2]=8;
for(i=3;i<=40;i++)
{
a[i]=2*a[i-1]+2*a[i-2];
}
while(scanf("%d",&n)!=EOF)
{
printf("%I64d\n",a[n]);
}
return 0;
}
最後更新：2017-04-03 08:26:21