题目链接：http://poj.org/problem?id=2506

本题用的java解的，因为涉及到大数问题，如果对java中的大数操作不熟悉请点这儿：链接

思路：地推公式f[i]=f[i-1]+2*f[i-2]

code:

import java.math.*;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		BigInteger a[] = new BigInteger[300];
		BigInteger b=new BigInteger("2");
		a[0]=BigInteger.valueOf(1);
		a[1]=BigInteger.valueOf(1);
		a[2]=BigInteger.valueOf(3);
		a[3]=BigInteger.valueOf(5);
		int n;
		
		for(int i=3;i<=255;i++)
		{
			a[i]=a[i-1].add(a[i-2].multiply(b));
		}
		while(cin.hasNext())
		{
			n=cin.nextInt();
			System.out.println(a[n]);
		}	
	}
}