poj 1205 ：Water Treatment Plants (DP+高精度)

import java.util.Scanner;
import java.math.*;
public class Main {
  public static void main(String[] args) {
    int n;
    Scanner cin = new Scanner(System.in);
    BigInteger[] a = new BigInteger[110];
    a[1] = BigInteger.valueOf(1);
    a[2] = BigInteger.valueOf(3);
    for (int i = 3; i <= 100; i++) {
      a[i] = a[i-1].multiply(BigInteger.valueOf(3)).subtract(a[i-2]);
    }
    while (cin.hasNextInt()) {
      n = cin.nextInt();
      System.out.println(a[n]);
    }
    cin.close();
  }
}