学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1041

高精度，f[n] = f[ n - 1  ] + f[  n - 2 ] * 2 ;

f[ 0 ] = 0 ; 

f[ 1 ] = 1 ;

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bitset>

using namespace std;

int num[ 1010 ][ 1010 ];

int main()
{
	num[ 1 ][ 0 ] = 0 ;
	num[ 2 ][ 0 ] = 1 ;
	for( int i = 3 ; i <= 1000 ; ++i )
	{
		for( int j = 0 ; j < 1000 ; ++j )
		{
			num[ i ][ j ] +=  num[ i - 1  ][ j ] + num[ i - 2 ][ j ] * 2 ;
			if( num[ i ][ j ] > 9 )
			{num[ i ][ j + 1 ] = num[ i ][ j ] / 10 ;
				num[ i ][ j ] %= 10 ;
				
			}
		}
	}
	
	int n ;
	while( cin >> n  )
	{
		if( n == 1 )
			cout << "0" <<endl ;
		else
		{
			 bool flag = true;
            for(int i=999;i>=0;i--)
            {
                if( num[n][i] && flag)
                {
                    flag = false;
                }
                if(!flag)
                cout << num[n][i] ;
            }
            cout << endl;
		}
	}
	return 0 ;
}