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

问总共有多少种处理情况，即不同又符合实际的><V组合。

 

思路：DP+高精度。DP部分，易得最右边城市的状态只可能用3种：>V, V, <。故分三种状态讨论，设dp[i][0]为第i个城市的状态为：> V ，dp[i][1]为：V ，dp[i][2]为：<。由实际流动的可能性可以得到状态转移方程：

dp[i][0] = dp[i-1][0] + dp[i-1][1]；

dp[i][1] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];

dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];

然后可以整理为：dp[i] = 3 * dp[i-1] + dp[i-2]。然后用java的BigInteger预处理就OK了。

以下是java代码：

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();
	}
}