UVA10862 - Connect the Cable Wires（递推 + java的大数）

浏览数：27 / 时间：2015年06月08日

题目大意：给你n座房子位于一条直线上，然后只给你一个cable service，要求每座房子都连上有线，方式可以是间接的通过这个房子的直接邻居连接（前提是它的邻居要连上有线），另外一种是直接连上cable service也是可以的。

解题思路：把后面的房子编号为1，前面的为n，假设我们要连1号房子，那么它有三种可能。
1、直接和cable service连接，那么就是加上f（n - 1）种（前面的n - 1座房子的组合方式）。
2、和2号房子连接不和cable service连接，那么又是f（n - 1)种。
3、和2号房子链接且和cable service连接，那么这就意味这2号房子不能和cable service链接，否则形成环了。这样就可以把1号和2号看成一个整体，并且和cable service有一条边。这样的情况就可以分两种：（1）、不和三号连，加上f（n - 2）。（2）和三号连，这样情况又回到情况3，说明这个是可以递归的。

所以f（n） = 2 f（n - 1) + f(n - 2) + f(n - 3) + .. + f(1) + 1.(递归到1的时候只有不和1号连接和与1号连接然后1号不和cable service这两种)
同样写出f（n - 1），相减得：f（n） = 3 $*$ f(n - 1) - f(n - 2); (n > 2).
边界f(2) = 3, f(1) = 1;3的2000次方会超过long long的，所以要用大数。

代码：

import java.util.*;
import java.math.*;
import java.io.*;

public class Main {

    static BigInteger f[] = new BigInteger[2005];

    public static void init() {

        f[1] = BigInteger.valueOf(1); 
        f[2] = BigInteger.valueOf(3);
        for (int i = 3; i <= 2000; i++)
            f[i] = BigInteger.valueOf(3).multiply(f[i - 1]).subtract(f[i - 2]);
    }

    public static void main(String args[]) {

        Scanner cin = new Scanner(System.in);
        int n;
        init();

        while (true) {

            n = cin.nextInt();
            if (n == 0)
                break;

            System.out.println(f[n]);
        }
    }
}