xindoo is
always here

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



题意:有n个城市,它们由一个污水处理系统连接着,每个城市可以选择

1、将左边城市过来的污水和右边城市过来的污水连同本身的污水排到河里  >V<

2、将左边来的污水连同自己的污水排到右边  >>

3、将右边来的污水连同自己的污水排到左边  <<


问总共有多少种处理情况,即不同又符合实际的><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();
	}
}
打赏
未经允许不得转载:XINDOO » poj 1205 :Water Treatment Plants (DP+高精度)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏