#include <stdio.h>
int a[300]={0},b[300]={0},c[300]={0},ans[300]={0};
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
int j,i,n;
scanf("%d",&n);
a[1]=1;
b[1]=2;
c[1]=4;
if(n<4)
{
if(n==1)printf("1\n");
if(n==2)printf("2\n");
if(n==3)printf("4\n");
}
else{
for(i=4;i<=n;i++)
{
for(j=1;j<=300;j++)
{
ans[j]+=a[j]+b[j]+c[j];
ans[j+1]+=ans[j]/10;
ans[j]%=10;
}
for(j=1;j<=300;j++)
{
a[j]=b[j];
b[j]=c[j];
c[j]=ans[j];
ans[j]=0;
}
}
for(i=300;i>=0;i--)
if(c[i])break;
for(;i>=1;i--)printf("%d",c[i]);
printf("\n");
}
return 0;
}
很简单的DP 但是竟然忘记高精度的写法了....