前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >poj 1205 :Water Treatment Plants (DP+高精度)

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

作者头像
xindoo
发布2021-01-21 18:33:50
2810
发布2021-01-21 18:33:50
举报
文章被收录于专栏:XINDOO的专栏XINDOO的专栏

题意:有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代码:

代码语言:javascript
复制
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();
	}
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2013-09-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档