典型的DP打表输出水题。。。不过用递归却会超时,ORZ
对于这样一个0,1序列,a1,a2,a3,...a(i-2),a(i-1),a(i)...
设f(i)为输入的数对应的结果
用DP做的话,假设f(i-2),f(i-1)已经知道了,那么求f(i)应该如下:
当取a(i)=0,那么结果肯定和f(i-1)是一样的,因为在后面追加的是0,肯定不会导致存在相邻;
当取a(i)=1,那么此时只要知道a(i-2)就可以了,因为我们可以使a(i-1)为0,这样就不会导致相邻的1了;
所以a[i]=a[i-1]+a[i-2];
#include <iostream>
#include <string>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int fabi[50];
void init()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
fabi[1]=2;
fabi[2]=3;
for (int j=3;j<=45;j++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
fabi[j]=fabi[j-1]+fabi[j-2];
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
int n,i=1,num;
init();
cin>>n;
while (n>0)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
cin>>num;
printf("Scenario #%d:\n",i++);
printf("%d\n\n",fabi[num]);
n--;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)