#include <iostream>
using namespace std;
long long s0,s1,s2,s3;
int main()
{
int i,n;
while(cin>>n)
{
s0=3;s1=1;
s2=1;s3=1;
for(i=2;i<=n;i++)
{
s2=s1*2;
s3=s1=s0;
s0=s1+s2+s3;
}
cout<<s0<<endl;
}
return 0;
}
原文：http://www.cnblogs.com/NYNU-ACM/p/4658268.html